- Library und Data
library(tidyverse)
library(dplyr)
library(data.table)
library(ggplot2)
library(reshape2)
library(rsample)
library(recommenderlab)
data(MovieLense)
- Explorative Datenanalyse
mx_user_film <- as(MovieLense, "matrix") # convert realratingmatrix to normal matrix
df_user_film <- as.data.frame(mx_user_film) # convert matrix to dataframe form
df_film_user <- as.data.frame(t(mx_user_film)) # transpose the dataframe: each row is a movie name, each column is a user
2.1 Welches sind die am häufigsten geschauten Genres/Filme?
df_21 <- df_film_user %>% mutate(cnt = rowSums(!is.na(df_film_user))) %>% arrange(desc(cnt)) %>% filter(cnt == max(cnt)) %>% select('cnt')
df_21
Die am häufigsten geschauten Filme ist Star Wars.
2.2 Wie verteilen sich die Kundenratings gesamthaft und nach Genres?
df_unlist <- data.frame(rating=unlist(df_film_user)) # unlist the dataframe
ggplot(df_unlist,aes(rating)) + geom_histogram() + # die Verteilung der Kundenratings gesamthaft
labs(x="Ratings", y="Count",title="Distribution of the user ratings") +
theme(plot.title = element_text(hjust = 0.5))
`stat_bin()` using `bins = 30`. Pick better value with `binwidth`.
Warning: Removed 1469760 rows containing non-finite values (stat_bin).

The above histogram of ratings distribution is left skewed, with the mode = 4.
mx_film_genre <- as.data.frame(MovieLenseMeta)
rownames(mx_film_genre) <- mx_film_genre$title
mx_film_genre <- as.matrix(mx_film_genre[,5:22]) # Movie Genre Matrix
mx_user_film[is.na(mx_user_film)] <- 0
mx_user_genre <- mx_user_film %*% mx_film_genre
mx_genre_user <- as.data.frame(t(mx_user_genre)) # a: Stärke Genre Kombination vollständig
mx_genre_user$summe <- rowSums(mx_genre_user) # new column "summe": summe user ratings of each genre
mx_genre_user <- cbind(genre = rownames(mx_genre_user), mx_genre_user)# new column "genre": genre name copied from rownames
ggplot(mx_genre_user,aes(summe,genre)) + geom_col() + labs(x= "summed ratings of all users", y="Genre",title="Distribution of the user ratings by genre combination") +
theme(plot.title = element_text(hjust = 0.5))

mx_genre_user <- mx_genre_user %>% select(-genre)
Above is the distribution of ratings by genre, “drama” has the highest summed ratings.
df_22 <- as.data.frame(t(mx_film_genre)) %>% mutate(cnt = rowSums(as.data.frame(t(mx_film_genre))))%>% arrange(desc(cnt)) # add new column: count for each genres
df_22 <- cbind(genres = rownames(df_22),df_22) # index as a column
rownames(df_22) <- 1:nrow(df_22) # generate new index
ggplot(df_22,aes(x = (reorder(genres,cnt)), y = cnt)) + geom_col() + coord_flip() +
labs(y="Number of Views", x="Genres",title="Distribution by genres") +
theme(plot.title = element_text(hjust = 0.5))

The plot above shows the distribution of views by genre. The genre drama has the highest number of views.
2.3 Wie verteilen sich die mittleren Kundenratings pro Film?
df_avg_rating_film <- df_film_user %>% mutate(avg_rating = rowMeans(df_film_user,na.rm = TRUE, dims = 1)) %>% select('avg_rating')
ggplot(df_avg_rating_film,aes(avg_rating)) + geom_histogram(binwidth = 1) + # die Verteilung
labs(x="Mean user-ratings per film", y="Count of films",title="Distribution of the mean user-ratings per film") +
theme(plot.title = element_text(hjust = 0.5))

The plot showed us that the mode of average ratings per film is 3. Most of movies have the average rating larger than 2.
2.4 Wie stark streuen die Ratings von individuellen Kunden?
df_avg_rating_user <- df_user_film %>% mutate(avg_rating = rowMeans(df_user_film,na.rm = TRUE, dims = 1)) %>% select('avg_rating')
ggplot(df_avg_rating_user,aes(avg_rating)) + geom_histogram(bins = 5) + # die Verteilung
labs(x="Mean user-ratings per user", y="Count of users",title="Distribution of the mean user-ratings per user")+
theme(plot.title = element_text(hjust = 0.5))

The plot shows the mode of average user ratings per user is 3. Most of the average ratings are 3 or 4.
2.5 Welchen Einfluss hat die Normierung der Ratings pro Kunde auf deren Verteilung?
df_avg_rating_user <- df_user_film %>% mutate(avg_rating = rowMeans(df_user_film,na.rm = TRUE, dims = 1)) %>% select('avg_rating')
ggplot(df_avg_rating_user,aes(avg_rating)) + geom_histogram(bins = 20) + # die Verteilung
labs(x="Mean ratings per user", y="Count of users",title="Distribution of the mean ratings per user")+
theme(plot.title = element_text(hjust = 0.5))

normalized_movielens <- as(normalize(MovieLense,method = "z-score"), "matrix")
normalized_movielens <- as.data.frame(normalized_movielens)
normalized_avg_rating_user <- normalized_movielens %>% mutate(avg_rating=rowMeans(normalized_movielens,na.rm=TRUE, dims=1)) %>% select('avg_rating')
ggplot(normalized_avg_rating_user,aes(avg_rating)) + geom_histogram(bins = 20) + # die Verteilung
labs(x="Mean normalized ratings per user", y="Count of users",title="Distribution of the mean normalized ratings per user") +
theme(plot.title = element_text(hjust = 0.5))

without normalization (first plot): the average ratings are slightly left skewed, with the mode of 3.8. The ratings vary a lot across different users.
with Z-score normalization (second plot): the average ratings per user are all around 0. This mean, the ratings from different users are normalized to the same scale, with the mean of 0, the standard deviation of 1. This will reduce the influence of rating habits of different users.
2.6 Welche strukturellen Charakteristika (z.B. Sparsity) und Auffälligkeiten zeigt die User-Item Matrix?
Recommender System data usually contains a large numbers of users(rows) and items (columns), but a single user interacts with only a small subset of the items. This means, the dataframe consists of many zero values, the structure is extremely sparse.
Vor Datenreduktion: 1664 Movies, 943 users, 93.82% Data are NA.
print(dim(df_user_film))
[1] 943 1664
print(sum(is.na(df_user_film))/(1663*942))
[1] 0.9382169
image(as(df_user_film,"matrix"), main = "sparsity of dataframe before reduction")

Nach Datenreduktion: 700 Movies, 400 users, 75.90% data are NA.
print(dim(df_reduced))
[1] 400 700
print(sum(is.na(df_reduced))/(700*400))
[1] 0.7589929
image(as(df_reduced,"matrix"),main = "sparsity of dataframe after reduction")

The two images above showed us the data sparsity before (first image) and after (second image) reduction. The blank pixels represent the NA, the color pixels represent the available values. By comparing the two images, we could see that the first image has more blank and less color pixels than the second one. This means the data after reduction is less sparse than before reduction. Data reduction has successfully reduced the data sparsity.
3.3 mittlere Kundenratings pro Film vor und nach Datenreduktion.
Before data reduction
df_avg_rating <- df_film_user %>% mutate(avg_rating = rowMeans(df_film_user,na.rm = TRUE, dims = 1)) %>% select('avg_rating')
ggplot(df_avg_rating,aes(avg_rating)) + geom_histogram(binwidth = 0.25) + # die Verteilung
labs(x="Mean ratings per film", y="Count",title="Before reduction: Distribution of the mean ratings by film") +
theme(plot.title = element_text(hjust = 0.5))

df_reduced_t <- as.data.frame(t(df_reduced))
df_reduced_avg_rating <- df_reduced_t%>% mutate(avg_rating = rowMeans(df_reduced_t,na.rm = TRUE, dims = 1)) %>% select('avg_rating')
ggplot(df_reduced_avg_rating,aes(avg_rating)) + geom_histogram(binwidth = 0.25) + # die Verteilung
labs(x="Mean ratings per film", y="Count",title="After reduction: Distribution of the mean ratings by film") +
theme(plot.title = element_text(hjust = 0.5))

After the data reduction, the average ratings are close to a left skewed normal distribution.
4 Analyse Ähnlichkeitsmatrix
4.1 Zerlege den reduzierten MovieLense Datensatz in ein disjunkte Trainings-und Testdatenset im Verhältnis 4:1
set.seed(465)
mx_reduced <- as.matrix(df_reduced)
rrm_reduced <- as(mx_reduced,"realRatingMatrix")
train_test <- evaluationScheme(rrm_reduced, method="split", train=0.8, k=1, given=20, goodRating=4)
# training data 80% of the users
rrm_reduced_train <- getData(train_test,"train")
# test data is 20% of the all users, the test data is splited into two parts: known test data and unknown test data
# the known portion returns specified 20 items per test user is used to predict ratings or films for the test users
rrm_reduced_known <- getData(train_test,"known")
# the unknown portion is used to compute the prediction error of the model
rrm_reduced_unknown <- getData(train_test,"unknown")
4.2 Trainiere ein IBCF Modell mit 30 Nachbarn und Cosine Similarity
model_IBCF <- Recommender(data = rrm_reduced_train,method="IBCF",parameter=list(normalize = "Z-score",method="Cosine",k=30))
4.3 Bestimme die Verteilung der Filme, welche bei IBCF für paarweise Ähnlichkeitsvergleiche verwendet werden. Determine the distribution of films used in IBCF for pairwise similarity comparisons
# Here only exhibit the first 50 rows and columns
get_model_IBCF <- getModel(model_IBCF)
image(get_model_IBCF$sim[1:50, 1:50], main = "Similarity of the first 50 rows and columns")

The similarity matrix is not symmetric. Each row has 30 elements larger than 0. In each column, the number of elements greater than 0 indicates how many times this film was included in the TOP list of other films.
IBCF_sim <- as.data.frame(colSums(get_model_IBCF$sim > 0))
colnames(IBCF_sim) <- "recommended_frequency" # frequency that the corresponding film is included in other films' TOP-N lists
ggplot(IBCF_sim, aes(x=IBCF_sim$recommended_frequency))+geom_histogram(fill="black", col="grey",binwidth = 5)+
labs(x = "Recommended frequency", y = "Count", title = "Distribution of recommended frequency per film") +
theme(plot.title = element_text(hjust = 0.5))
Warning: Use of `IBCF_sim$recommended_frequency` is discouraged. Use `recommended_frequency` instead.

The plot displays the distribution of films by how many times the corresponding film included in the TOP list of other films. For instance, about 52 films are not included in any TOP list of other films, about 100 films are included in the TOP lists of 5 films. The highest frequency is about 160.
4.4 Bestimme die Filme, die am häufigsten in der Cosine-Ähnlichkeitsmatrix auftauchen und analysiere deren Vorkommen und Ratings im reduzierten Datensatz.
die am häufigsten Film in der Cosine-Ähnlichkeitsmatrix
# die 10 am häufigsten Filme in der Cosine Ähnlichkeitsmatrix, i.e. die Filme mit der höheste sum Ähnlichkeits
high_freq_film <- IBCF_sim %>% mutate(film = rownames(IBCF_sim)) %>% arrange(desc(recommended_frequency)) %>% slice(0:10) %>% select(film,recommended_frequency)
high_freq_film
The Mouse Hunt is the most often recommended film.
die Vorkommen und Ratings in reduzierten Datensatz
t <- df_reduced_t %>% mutate(is_NA = rowSums(is.na(df_reduced_t)),not_NA = rowSums(!is.na(df_reduced_t)),occurrence = rowSums(!is.na(df_reduced_t))/dim(df_reduced_t)[2], film = rownames(df_reduced_t)) %>% select(is_NA,not_NA,occurrence,film)
Occurrence <- left_join(high_freq_film,t,by = "film") %>% select(film,recommended_frequency,occurrence)
t2 <- df_reduced_t %>% mutate(film = rownames(df_reduced_t), avg_rating = rowMeans(df_reduced_t,na.rm=TRUE))%>% select(film,avg_rating)
Occurrence <- left_join(Occurrence,t2,by = "film")
Occurrence # occurrence: not_NA / user number, the user ratio that rated this film
recommended_frequency: the frequanecy that this item appears in the top-n recommendation list of other users.
occurrence: ratio that the film is rated to all users
avg_rating: the average rating of each film
From the result, we could see that, there are no direct relationship between the three variables. The most often recommended film Mouse Hunt has a relatively low average rating 2.32, and medium occurrence.
5 Analyse Top-N Listen IBCF vs UBCF Vergleiche und diskutiere Top N Empfehlungen von IBCF und UBCF Modellen mit 30 Nachbarn und Cosine Similarity für den reduzierten Datensatz. Analysis Top-N lists IBCF vs UBCF. Compare and discuss top N recommendations from IBCF and UBCF models with 30 neighbors and cosine similarity for the reduced data set.
5.1 Berechne Top 15 Empfehlungen für Testkunden mit IBCF und UBCF
## top-N recommendations for testdata users with IBCF
Pred_IBCF <- predict(object = model_IBCF, newdata = rrm_reduced_known, n = 15,type=c("topNList"))
TOP15_IBCF <- sapply(Pred_IBCF@items, function(x) {colnames(df_reduced)[x]})
TOP15_IBCF[,1:2] # here only display the top 15 recommendations for the first two test users
655
[1,] "Titanic (1997)"
[2,] "Indiana Jones and the Last Crusade (1989)"
[3,] "Forrest Gump (1994)"
[4,] "Braveheart (1995)"
[5,] "Terminator 2: Judgment Day (1991)"
[6,] "Die Hard (1988)"
[7,] "It's a Wonderful Life (1946)"
[8,] "Hunt for Red October, The (1990)"
[9,] "Aladdin (1992)"
[10,] "Reservoir Dogs (1992)"
[11,] "Good, The Bad and The Ugly, The (1966)"
[12,] "Chasing Amy (1997)"
[13,] "Raging Bull (1980)"
[14,] "Close Shave, A (1995)"
[15,] "Chinatown (1974)"
276
[1,] "English Patient, The (1996)"
[2,] "Twelve Monkeys (1995)"
[3,] "Rock, The (1996)"
[4,] "Star Trek: First Contact (1996)"
[5,] "Fugitive, The (1993)"
[6,] "Forrest Gump (1994)"
[7,] "Birdcage, The (1996)"
[8,] "Jurassic Park (1993)"
[9,] "Dances with Wolves (1990)"
[10,] "Trainspotting (1996)"
[11,] "Fifth Element, The (1997)"
[12,] "Face/Off (1997)"
[13,] "Dr. Strangelove or: How I Learned to Stop Worrying and Love the Bomb (1963)"
[14,] "This Is Spinal Tap (1984)"
[15,] "That Thing You Do! (1996)"
# predict with UBCF
model_UBCF <- Recommender(rrm_reduced_train,method="UBCF",param=list(normalize = "Z-score",method="Cosine",nn=30)) #model
# top-N recommendations for testdata users with UBCF
Pred_UBCF <- predict(object = model_UBCF, newdata = rrm_reduced_known, n = 15,type=c("topNList"))
#TOP15_UBCF <- as(Pred_UBCF, "list")
TOP15_UBCF <- sapply(Pred_UBCF@items, function(x) {colnames(df_reduced)[x]})
TOP15_UBCF[,1:2] # here only display the top 15 recommendations for the first two test users
655 276
[1,] "Three Colors: Red (1994)" "Bridges of Madison County, The (1995)"
[2,] "Three Colors: White (1994)" "Dazed and Confused (1993)"
[3,] "Wings of Desire (1987)" "Big Lebowski, The (1998)"
[4,] "Antonia's Line (1995)" "Bronx Tale, A (1993)"
[5,] "Blue in the Face (1995)" "Fierce Creatures (1997)"
[6,] "M (1931)" "Postman, The (1997)"
[7,] "Winnie the Pooh and the Blustery Day (1968)" "Little Princess, A (1995)"
[8,] "As Good As It Gets (1997)" "Nixon (1995)"
[9,] "Wrong Trousers, The (1993)" "Strictly Ballroom (1992)"
[10,] "Sunset Blvd. (1950)" "Reservoir Dogs (1992)"
[11,] "Apartment, The (1960)" "Before Sunrise (1995)"
[12,] "East of Eden (1955)" "Secrets & Lies (1996)"
[13,] "Farewell My Concubine (1993)" "Red Corner (1997)"
[14,] "Postino, Il (1994)" "Crumb (1994)"
[15,] "Nosferatu (Nosferatu, eine Symphonie des Grauens) (1922)" "Apt Pupil (1998)"
5.2 Vergleiche die Top 15 Empfehlungen und deren Verteilung und diskutiere Gemeinsamkeiten und Unterschiede zwischen IBCF und UBCF für alle Testkunden.
From above the result for first two users, we could see that the top 15 recommendations for the same user between the IBCF and UBCF models are completely different.
Compare the top 15 recommendations for all test users First identify the most recommended movies in the TOP-15 list from all test users.
# generate frequency tables : all the recommendation films with the corresponding frequencies
film_freq_IBCF <- as.data.frame(table(as.factor(TOP15_IBCF)))
colnames(film_freq_IBCF) <- c("Film_by_IBCF", "Frequency")
film_freq_UBCF <- as.data.frame(table(as.factor(TOP15_UBCF)))
colnames(film_freq_UBCF) <- c("Film_by_UBCF", "Frequency")
head(film_freq_IBCF %>% arrange(desc(Frequency)),15)
head(film_freq_UBCF %>% arrange(desc(Frequency)),15)
ggplot(head(film_freq_IBCF %>% arrange(desc(Frequency)),15),aes(x = reorder(Film_by_IBCF,Frequency), y = Frequency)) + geom_col() + coord_flip() +
labs(y="Frequency", x="Film",title="Distribution of the Top-15 films for all the users with IBCF") +
theme(plot.title = element_text(hjust = 0.5))

ggplot(head(film_freq_UBCF %>% arrange(desc(Frequency)),15),aes(x = reorder(Film_by_UBCF,Frequency), y = Frequency)) + geom_col() + coord_flip() +
labs(y="Frequency", x="Film",title="Distribution of the Top-15 films for all the users with UBCF") +
theme(plot.title = element_text(hjust = 0.5))

The maximum recommended frequency with IBCF and UBCF are 26 and 28 respectively, and minimum of 15 and 13. However comparing to the IBCF, the distribution in UBCF has a longer tail. This means with the UBCF model, some movies are recommended much more often than the others.
6 Analyse Top-N Listen Ratings Untersuche den Einfluss von Ratings (ordinale vs binäre Ratings) und Modelltyp (IBCF vs UBCF) auf Top N Empfehlungen für den reduzierten Datensatz.
6.1 Vergleiche den Anteil übereinstimmender Empfehlungen der Top 15 Liste für IBCF vs UBCF, beide mit ordinalem Rating und Cosine Similarity für alle Testkunden
# the test user "unknown" ratings
mx_reduced_unknown <- as(rrm_reduced_unknown,"matrix")
# predict the ratings of test users by IBCF and UBCF
pred_rating_IBCF <- as(predict(object = model_IBCF, newdata = rrm_reduced_known, n = 15,type="ratings"),"matrix")
pred_rating_UBCF <- as(predict(object = model_UBCF, newdata = rrm_reduced_known, n = 15,type="ratings"),"matrix")
# evaluate recommendations on "unknown" ratings
acc_IB <- calcPredictionAccuracy(predict(object = model_IBCF, newdata = rrm_reduced_known, n = 15,type="ratings"),rrm_reduced_unknown)
acc_UB <- calcPredictionAccuracy(predict(object = model_UBCF, newdata = rrm_reduced_known, n = 15,type="ratings"),rrm_reduced_unknown)
acc_ordinal <- rbind(acc_IB,acc_UB)
rownames(acc_ordinal) <- c("IBCF ordinal","UBCF ordinal")
acc_ordinal
RMSE MSE MAE
IBCF ordinal 1.292176 1.669719 0.9504537
UBCF ordinal 1.073440 1.152273 0.8403449
the UBCF model with ordinal ratings and cosine similarity has better accuracy.
6.2 Vergleiche den Anteil übereinstimmender Empfehlungen der Top 15 Liste für IBCF vs UBCF, beide mit binärem Rating und Jaccard Similarity für alle Testkunden
# convert the reduced dataset to binary: ratings > 3 converted as 1, ratings <= 3 converted as 0
df_reduced_bi <- df_reduced
df_reduced_bi[df_reduced_bi <= 3] <- 0
df_reduced_bi[df_reduced_bi > 3] <- 1
set.seed(468)
mx_reduced_bi <- as.matrix(df_reduced_bi)
rrm_reduced_bi <- as(mx_reduced_bi,"realRatingMatrix")
train_test_bi <- evaluationScheme(rrm_reduced_bi, method="split", train=0.8, k=1, given=20)
# training data 80% of the users
rrm_reduced_train_bi <- getData(train_test_bi,"train")
# test data is 20% of the all users, the test data is splited into two parts: known test data and unknown test data
# the known portion returns specified 20 items per test user is used to predict ratings or films for the test users
rrm_reduced_known_bi <- getData(train_test_bi,"known")
# the unknown portion is used to compute the prediction error of the model
rrm_reduced_unknown_bi <- getData(train_test_bi,"unknown")
# train the IBCF or UBCF model on training dataset
model_IBCF_bi <- Recommender(data = rrm_reduced_train_bi,method="IBCF",parameter=list(normalize = "Z-score",method="Jaccard",k=30))
model_UBCF_bi <- Recommender(data = rrm_reduced_train_bi,method="UBCF",parameter=list(normalize = "Z-score",method="Jaccard",nn=30))
# predict the ratings of test users by IBCF and UBCF
pred_rating_IBCF_bi <- as(predict(object = model_IBCF_bi, newdata = rrm_reduced_known_bi, n = 15,type="ratings"),"matrix")
pred_rating_UBCF_bi <- as(predict(object = model_UBCF_bi, newdata = rrm_reduced_known_bi, n = 15,type="ratings"),"matrix")
# the test user "unknown" ratings
mx_reduced_unknown_bi <- as(rrm_reduced_unknown_bi,"matrix")
# evaluate recommendations on "unknown" ratings
acc_IB_bi <- calcPredictionAccuracy(predict(object = model_IBCF_bi, newdata = rrm_reduced_known_bi, n = 15,type="ratings"),rrm_reduced_unknown_bi)
acc_UB_bi <- calcPredictionAccuracy(predict(object = model_UBCF_bi, newdata = rrm_reduced_known_bi, n = 15,type="ratings"),rrm_reduced_unknown_bi)
acc_bi <- rbind(acc_IB_bi,acc_UB_bi)
rownames(acc_bi) <- c("IBCF binary","UBCF binary")
acc_bi
RMSE MSE MAE
IBCF binary 0.6302688 0.3972388 0.3976143
UBCF binary 0.4748717 0.2255031 0.3975344
the UBCF model with binary ratings and cosine similarity has better accuracy.
6.3 Vergleiche den Anteil übereinstimmender Empfehlungen der Top 15 Liste für UBCF mit ordinalem (Cosine Similarity) vs binärem Rating (Jaccard Similarity) für alle Testkunden.
rbind(acc_ordinal,acc_bi)
RMSE MSE MAE
IBCF ordinal 1.2921763 1.6697195 0.9504537
UBCF ordinal 1.0734398 1.1522730 0.8403449
IBCF binary 0.6302688 0.3972388 0.3976143
UBCF binary 0.4748717 0.2255031 0.3975344
The model with binary ratings have largely improved the accuracy comparing to the models with ordinal ratings.
7 Analyse Top-N Listen -IBCF vs SVD Aufgabe: Vergleiche Memory-based IBCF und Modell-based SVD Recommenders bezüglich Überschneidung ihrer Top-N Empfehlungen für die User-Item Matrix des reduzierten Datensatzes (Basis: IBCF mit 30 Nachbarn und Cosine Similarity).
- Vergleiche wie sich der Anteil übereinstimmender Empfehlungen der Top-15 Liste für IBCF vs verschiedene SVD Modelle verändert, wenn die Anzahl der Singulärwerte für SVD von 10 auf 20, 30, 40, 50 verändert wird.
# SVD MODEL
model_SVD_10 <- Recommender(data = rrm_reduced_train,method="SVD",parameter=list(normalize = "Z-score",k=10))
model_SVD_20 <- Recommender(data = rrm_reduced_train,method="SVD",parameter=list(normalize = "Z-score",k=20))
model_SVD_30 <- Recommender(data = rrm_reduced_train,method="SVD",parameter=list(normalize = "Z-score",k=30))
model_SVD_40 <- Recommender(data = rrm_reduced_train,method="SVD",parameter=list(normalize = "Z-score",k=40))
model_SVD_50 <- Recommender(data = rrm_reduced_train,method="SVD",parameter=list(normalize = "Z-score",k=50))
# evaluate recommendations on "unknown" ratings
acc_SVD_10 <- calcPredictionAccuracy(predict(object = model_SVD_10, newdata = rrm_reduced_known, n = 15,type="topNList"),rrm_reduced_unknown,given=20,goodRating = 4)
acc_SVD_20 <- calcPredictionAccuracy(predict(object = model_SVD_20, newdata = rrm_reduced_known, n = 15,type="topNList"),rrm_reduced_unknown,given=20,goodRating = 4)
acc_SVD_30 <- calcPredictionAccuracy(predict(object = model_SVD_30, newdata = rrm_reduced_known, n = 15,type="topNList"),rrm_reduced_unknown,given=20,goodRating = 4)
acc_SVD_40 <- calcPredictionAccuracy(predict(object = model_SVD_40, newdata = rrm_reduced_known, n = 15,type="topNList"),rrm_reduced_unknown,given=20,goodRating = 4)
acc_SVD_50 <- calcPredictionAccuracy(predict(object = model_SVD_50, newdata = rrm_reduced_known, n = 15,type="topNList"),rrm_reduced_unknown,given=20,goodRating = 4)
acc_IBCF_top15 <- calcPredictionAccuracy(predict(object = model_IBCF, newdata = rrm_reduced_known, n = 15,type="topNList"),rrm_reduced_unknown,given=20,goodRating = 4)
acc_SVD_IB <- rbind(acc_SVD_10,acc_SVD_20,acc_SVD_30,acc_SVD_40,acc_SVD_50,acc_IBCF_top15)
rownames(acc_SVD_IB) <- c("SVD_k_10","SVD_k_20","SVD_k_30","SVD_k_40","SVD_k_50","IBCF_cos_k_30")
acc_SVD_IB
TP FP FN TN N precision recall TPR FPR
SVD_k_10 6.8375 8.1625 74.5500 590.4500 680 0.4558333 0.09185763 0.09185763 0.01346130
SVD_k_20 6.0625 8.9375 75.3250 589.6750 680 0.4041667 0.07887917 0.07887917 0.01478280
SVD_k_30 5.9250 9.0750 75.4625 589.5375 680 0.3950000 0.07734909 0.07734909 0.01500427
SVD_k_40 6.0250 8.9750 75.3625 589.6375 680 0.4016667 0.07828355 0.07828355 0.01484067
SVD_k_50 5.5375 9.4625 75.8500 589.1500 680 0.3691667 0.07166389 0.07166389 0.01567906
IBCF_cos_k_30 5.7875 9.2125 75.6000 589.4000 680 0.3858333 0.07194244 0.07194244 0.01518621
The model with SVD and 10 neighbors have the best precision and recall.
SVD k=10 > SVD k=20 > SVD k=40 > SVD k=30 > IBCF cosine k=30 > SVD k=50
8 Wahl des optimalen Recommenders Aufgabe: Bestimme aus 5 unterschiedlichen Modellen das hinsichtlich Top-N Empfehlungen beste Modell. Begründe deine Modellwahlen aufgrund der bisher gemachten Erkenntnisse und verwende als 6. Modell einen Top-Movie Recommender (Basis: reduzierter Datensatz).
8.1 Verwende für die Evaluierung 10-fache Kreuzvalidierung
#create 10-fold cross validation scheme
set.seed(6954)
scheme <- evaluationScheme(rrm_reduced, method="cross", k=10, given=20, goodRating=4)
# evaluate with different methods
cv_IBCF <- evaluate(scheme, method="IBCF", type = "topNList",parameter=list(normalize = "Z-score",method="cosine",k=30),n=15)
IBCF run fold/sample [model time/prediction time]
1 [2.01sec/0.04sec]
2 [1.23sec/0.04sec]
3 [1.65sec/0.04sec]
4 [0.89sec/0.03sec]
5 [1.28sec/0.04sec]
6 [1.25sec/0.04sec]
7 [1sec/0.03sec]
8 [1.06sec/0.03sec]
9 [1.07sec/0.04sec]
10 [1.32sec/0.11sec]
cv_UBCF <- evaluate(scheme, method="UBCF", type = "topNList",parameter=list(normalize = "Z-score",method="cosine",nn=30),n=15)
UBCF run fold/sample [model time/prediction time]
1 [0.03sec/0.25sec]
2 [0.02sec/0.22sec]
3 [0.01sec/0.24sec]
4 [0.01sec/0.28sec]
5 [0.03sec/0.23sec]
6 [0.03sec/0.2sec]
7 [0.03sec/0.22sec]
8 [0.01sec/0.22sec]
9 [0.03sec/0.23sec]
10 [0.03sec/0.28sec]
cv_SVD <- evaluate(scheme, method="SVD", type = "topNList",parameter=list(normalize = "Z-score",k=30),n=15)
SVD run fold/sample [model time/prediction time]
1 [0.24sec/0.03sec]
2 [0.27sec/0.05sec]
3 [0.23sec/0.05sec]
4 [0.26sec/0.05sec]
5 [0.26sec/0.13sec]
6 [0.36sec/0.08sec]
7 [0.31sec/0.03sec]
8 [0.25sec/0.05sec]
9 [0.28sec/0.04sec]
10 [0.27sec/0.11sec]
cv_RANDOM <- evaluate(scheme,method="RANDOM",type="topNList",n=15)
RANDOM run fold/sample [model time/prediction time]
1 [0sec/0.05sec]
2 [0sec/0.05sec]
3 [0sec/0.05sec]
4 [0.01sec/0.03sec]
5 [0sec/0.03sec]
6 [0sec/0.05sec]
7 [0.01sec/0.03sec]
8 [0sec/0.03sec]
9 [0sec/0.03sec]
10 [0sec/0.03sec]
cv_POP <- evaluate(scheme, method="POPULAR", type = "topNList",parameter=list(normalize = "Z-score"),n=15)
POPULAR run fold/sample [model time/prediction time]
1 [0.03sec/0.19sec]
2 [0.03sec/0.17sec]
3 [0.09sec/0.14sec]
4 [0.03sec/0.11sec]
5 [0.03sec/0.15sec]
6 [0.03sec/0.15sec]
7 [0.04sec/0.17sec]
8 [0.05sec/0.17sec]
9 [0.03sec/0.17sec]
10 [0.03sec/0.14sec]
# get the averaged evaluation results
Result_81 <- rbind(avg(cv_IBCF),avg(cv_UBCF),avg(cv_SVD),avg(cv_RANDOM),avg(cv_POP))
rownames(Result_81) <- c("IBCF","UBCF","SVD","RANDOM","POPULAR")
Result_81
TP FP FN TN N precision recall TPR FPR n
IBCF 5.9325 9.0675 78.8625 586.1375 680 0.3955000 0.07568762 0.07568762 0.01501425 15
UBCF 2.0375 12.9625 82.7575 582.2425 680 0.1358333 0.02445926 0.02445926 0.02178287 15
SVD 5.8900 9.1100 78.9050 586.0950 680 0.3926667 0.07739847 0.07739847 0.01513654 15
RANDOM 3.7675 11.2325 81.0275 583.9725 680 0.2511667 0.04431406 0.04431406 0.01871414 15
POPULAR 7.7900 7.2100 77.0050 587.9950 680 0.5193333 0.10232189 0.10232189 0.01184747 15
The model with popular method has the best precision and recall.
Popular > IBCF ~ SVD > RANDOM > UBCF
8.2 Begründe deine Wahl der Performance Metrik,
Higher precision means that an algorithm returns more relevant results than irrelevant ones, and high recall means that an algorithm returns most of the relevant results (whether or not irrelevant ones are also returned).
A perfect precision score of 1.0 means that every result retrieved was relevant (but says nothing about whether all relevant documents were retrieved) whereas a perfect recall score of 1.0 means that all relevant documents were retrieved by the search (but says nothing about how many irrelevant documents were also retrieved)
The model Popular returns the highest score of both precision and recall.
Popular > SVD ~ IBCF > RANDOM > UBCF
8.3 Analysiere das beste Modell für Top-N Recommendations mit N gleich 10, 15, 20, 25 und 30,
POP_results <- evaluate(scheme, method="POPULAR", type = "topNList",parameter=list(normalize = "Z-score"),n=c(10,15,20,25,30))
POPULAR run fold/sample [model time/prediction time]
1 [0.05sec/0.26sec]
2 [0.05sec/0.19sec]
3 [0.03sec/0.11sec]
4 [0.03sec/0.13sec]
5 [0.03sec/0.14sec]
6 [0.03sec/0.12sec]
7 [0.04sec/0.15sec]
8 [0.03sec/0.16sec]
9 [0.03sec/0.15sec]
10 [0.03sec/0.14sec]
avg_POP_results <- avg(POP_results)
avg_POP_results
TP FP FN TN N precision recall TPR FPR n
[1,] 5.4325 4.5675 79.3625 590.6375 680 0.5432500 0.07252614 0.07252614 0.007496331 10
[2,] 7.7900 7.2100 77.0050 587.9950 680 0.5193333 0.10232189 0.10232189 0.011847466 15
[3,] 9.8050 10.1950 74.9900 585.0100 680 0.4902500 0.12716681 0.12716681 0.016767608 20
[4,] 11.6650 13.3350 73.1300 581.8700 680 0.4666000 0.15028748 0.15028748 0.021961408 25
[5,] 13.4225 16.5775 71.3725 578.6275 680 0.4474167 0.17192212 0.17192212 0.027340196 30
When I increase the N, the “recall” is getting better (larger value), but the “precision” is getting worse (smaller value).
8.4 Optimiere dein bestes Modell hinsichtlich Hyperparameter. Hinweis: Verwende für den Top-Movie Recommender die Filme mit den höchsten Durchschnittsratings.
# films with only the highest average ratings (ratings > 3)
df_top_avg <- as.data.frame(t(df_reduced))
df_top_avg <- df_top_avg %>% mutate(avg_rating = rowMeans(df_top_avg,na.rm=TRUE,dims=1))%>% arrange(desc(avg_rating))%>% filter(avg_rating>3) %>% select(-avg_rating)
rrm_top_avg <- as(t(df_top_avg),"realRatingMatrix")
set.seed(846954)
scheme_top_avg <- evaluationScheme(rrm_top_avg, method="cross", k=10, given=20, goodRating=4)
# the model Popular has only one parameter: normalize. Here I will compare two normalization methods: z-score and center
POP_top_avg_z <- avg(evaluate(scheme_top_avg, method="POPULAR", type = "topNList",parameter=list(normalize = "Z-score"),n=c(10,15,20,25,30)))
POPULAR run fold/sample [model time/prediction time]
1 [0.03sec/0.11sec]
2 [0.04sec/0.12sec]
3 [0.04sec/0.12sec]
4 [0.06sec/0.17sec]
5 [0.05sec/0.19sec]
6 [0.03sec/0.12sec]
7 [0.03sec/0.14sec]
8 [0.05sec/0.14sec]
9 [0.03sec/0.17sec]
10 [0.04sec/0.18sec]
POP_top_avg_center <- avg(evaluate(scheme_top_avg, method="POPULAR", type = "topNList",parameter=list(normalize = "center"),n=c(10,15,20,25,30)))
POPULAR run fold/sample [model time/prediction time]
1 [0.01sec/0.13sec]
2 [0.03sec/0.23sec]
3 [0.02sec/0.12sec]
4 [0sec/0.14sec]
5 [0.02sec/0.12sec]
6 [0sec/0.14sec]
7 [0.01sec/0.13sec]
8 [0.01sec/0.13sec]
9 [0.02sec/0.15sec]
10 [0.01sec/0.19sec]
diff_z_center <- cbind((POP_top_avg_z - POP_top_avg_center)[,6:7],POP_top_avg_z[,10])
POP_top_avg_z; POP_top_avg_center; diff_z_center
TP FP FN TN N precision recall TPR FPR n
[1,] 5.3750 4.6250 74.2000 461.8000 546 0.5375000 0.07540714 0.07540714 0.009630248 10
[2,] 7.6650 7.3350 71.9100 459.0900 546 0.5110000 0.10625880 0.10625880 0.015300434 15
[3,] 9.5875 10.4125 69.9875 456.0125 546 0.4793750 0.13255558 0.13255558 0.021790133 20
[4,] 11.3750 13.6250 68.2000 452.8000 546 0.4550000 0.15450913 0.15450913 0.028541074 25
[5,] 12.9425 17.0575 66.6325 449.3675 546 0.4314167 0.17375578 0.17375578 0.035781723 30
TP FP FN TN N precision recall TPR FPR n
[1,] 5.380 4.620 74.195 461.805 546 0.5380000 0.07560488 0.07560488 0.009622775 10
[2,] 7.705 7.295 71.870 459.130 546 0.5136667 0.10685028 0.10685028 0.015212167 15
[3,] 9.585 10.415 69.990 456.010 546 0.4792500 0.13201246 0.13201246 0.021785083 20
[4,] 11.390 13.610 68.185 452.815 546 0.4556000 0.15485525 0.15485525 0.028504659 25
[5,] 13.040 16.960 66.535 449.465 546 0.4346667 0.17484967 0.17484967 0.035553745 30
precision recall
[1,] -0.000500000 -0.0001977426 10
[2,] -0.002666667 -0.0005914847 15
[3,] 0.000125000 0.0005431183 20
[4,] -0.000600000 -0.0003461215 25
[5,] -0.003250000 -0.0010938851 30
Here I tried to optimize the popular model through the normalization parameter. The two normaliazation methods z-score and center have very similiar performance on the precision and recall. The models with z-score has slightly better performance than the center normalization with n = 10, 15, 25, 30. The model with center normalization performed a bit better with n = 20.
9 Implementierung Ähnlichkeitsmatrix
Aufgabe DIY: Implementiere eine Funktion zur effizienten Berechnung von sparsen Ähnlichkeitsmatrizen für IBCF RS und analysiere die Resultate für 100 zufällig gewählte Filme.
9.1 Implementiere eine Funktion, um für ordinale Ratings effizient die Cosine Similarity zu berechnen,
cos_similarity <- function(mx){
n <- dim(mx)[2]
mx_0 <- mx
mx_0[is.na(mx_0)] <- 0
sim_mx <- matrix(1:n^2, nrow = n)
for(i in 1:n){
for(j in 1:n){
numerator <- t(mx_0[,i]) %*% mx_0[,j]
denominator <- sqrt(sum(mx_0[,i]^2))*sqrt(sum(mx_0[,j]^2))
sim_mx[i,j] <- numerator/denominator
}
}
return(sim_mx)
}
cos_sim_reduced_1 <- cos_similarity(df_reduced)
9.2 Implementiere eine Funktion, um für binäre Ratings effizient die Jaccard Similarity zu berechnen,
Jacc_similarity <- function(mx){
mx_bi <- mx
mx_bi[mx_bi <= 3] <- 0
mx_bi[is.na(mx_bi)] <- 0 # the NA and ratings <= 3 all converted as 0
mx_bi[mx_bi > 3] <- 1 # the ratings > 3 (which shows a preference) converted as 1
n <- dim(mx_bi)[2]
sim_mx <- matrix(1:n^2, nrow = n) # create a matrix with dimention of n x n for similarity
for(i in 1:n){
for(j in 1:n){
diff <- sum(abs(mx_bi[,i] - mx_bi[,j])) # the sum of absolute difference between two vectors: since the pairs are either same or with the difference of 1, this means the result shows also how many pairs are different.
sim_mx[i,j] <- 1 - diff/n
}
}
return(sim_mx)
}
Jacc_sim_reduced <- Jacc_similarity(df_reduced) # a 700 x 700 similarity matrix
9.3 Vergleiche deine Implementierung der Cosine-basierten Ähnlichkeitsmatrix für ordinale Kundenratings mit der korrespondierenden via Open Source Paketen erzeugten Ähnlichkeitsmatrix,
mx_reduced_0 <- mx_reduced
mx_reduced_0[is.na(mx_reduced_0)]<-0 # replace NA as 0
cos_sim_reduced_2 <- as.matrix(similarity(as(mx_reduced_0,"realRatingMatrix"), method = "cosine", which = "items")) # calculate the cosine similarity matrix by open source package
# Since the cos similarity matrix by this method use 0 for all the diagonal elements, where all are 1 by the upper function to remove this effect, here i will refill the diagonal with 1
diag(cos_sim_reduced_2)<-1
compare_two_cos_sim_methods <- all.equal(cos_sim_reduced_1, cos_sim_reduced_2, tolerance = 1e-10,check.attributes = FALSE)
compare_two_cos_sim_methods
[1] TRUE
The cosine similarity matrices by two different methods are equal (with tolerance of 1e-10).
9.4 Vergleiche und diskutiere die Unterschiede deiner mittels Cosine Similarity erzeugten Ähnlichkeitsmatrizen für ordinale und normierte Kundenratings mit der Jaccard-basierten Ähnlichkeitsmatrix.
compare_cos_Jacc <- all.equal(cos_sim_reduced_1,Jacc_sim_reduced,tolerance = 1e-3,check.attributes = FALSE)
compare_cos_Jacc
[1] "Mean relative difference: 2.480877"
The mean relative difference between cosine similarity and jaccard similarity is 2.48.
Jaccard similarity takes only the unique set of items. The cosine similarity takes the total length of the vectors.
10 Implementierung Top-N Metriken
Aufgabe DIY: Implementiere Funktionen für die Beurteilung der Top-N Metriken Precision und Recall sowie für alle Kunden der Item-space Coverage und Novelty und teste diese mit IBCF Recommendations (Basis: reduzierter Datensatz; N = 5, 10, 15, 20, 25, 30)
10.1 Implementiere eine Funktion, um aus Top-N Listen für alle Kunden die Item-space Coverage@N und Novelty@N eines Recommenders zu beurteilen und teste diese.
calc_topn_metrics <- function(mx,split_ratio,N){ # mx: U_I data; split_ratio:train data proportion; n: Top-N
rrm <- as(mx,"realRatingMatrix")
# split train, test-known, test_unknown data
train_test <- evaluationScheme(rrm, method="split", train=split_ratio, k=1, given=20,goodRating=4)
rrm_train <- getData(train_test,"train")
rrm_known <- getData(train_test,"known")
rrm_unknown <- getData(train_test,"unknown")
# IBCF model
model_IBCF <-Recommender(data = rrm_train,method="IBCF",parameter=list(normalize = "Z-score",method="Cosine",k=10))
# predict Top-N recommendation list
pred_IBCF <- predict(object = model_IBCF, newdata = rrm_known, n = N,type="topNList")
####################################
### accuracy: evaluate the recommendations on "unknown" ratings with metrics precision and recall
acc_IBCF <- calcPredictionAccuracy(predict(object = model_IBCF, newdata = rrm_known, n = N,type="topNList"),rrm_unknown,given=20,goodRating = 4)
acc_IBCF <- t(as.data.frame(acc_IBCF))
rownames(acc_IBCF) <- NULL
####################################
### item-space coverage: how many percentage of films(from the train data) are in the top-n recommendation lists
# top n lists for every user
TOP_N_list <- sapply(pred_IBCF@items, function(x) {colnames(as(rrm_known,"matrix"))[x]})
# unique predicted film list of all test users
uniq_film_test <- reshape2::melt(as(TOP_N_list,"matrix")) %>% rename(UserID = Var2, rank = Var1, Film_name = value)%>%distinct(Film_name) # unique film list recommended in test data
# unique film list of the train data
uniq_film_train <- as.data.frame(t(mx))
uniq_film_train$cnt <- rowSums(!is.na(uniq_film_train)) # count not NA for each film
uniq_film_train <- uniq_film_train %>% filter(cnt>0) # remove the film without any ratings
# calculate the item-space coverage
coverage <- dim(uniq_film_test)[1] / dim(uniq_film_train)[1] # the coverage
coverage <- as.data.frame(coverage)
colnames(coverage) <- "coverage"
####################################
### novelty for a given user: ratio of unknown items in the top-n list
novelty_table <- data.frame() # an empty dataframe, will be filled with novelty values
df <- as.data.frame(mx)
pred_IBCF_all_user <- predict(object = model_IBCF, newdata = rrm, n = N,type="topNList") # predict for all users
TOP_N_list_all_user <- sapply(pred_IBCF_all_user@items, function(x) {colnames(mx)[x]}) # top-n list for all users
# df_1: replace the not NA values to the corresponding column name
for(i in 1:dim(mx)[1]){
df_i <- as.data.frame(t(mx))#
df_i$Film <- colnames(mx)
df_i <- df_i[,c(i,(dim(mx)[1]+1))] %>% filter(complete.cases(.)) # list of user-i rated films
df_i$Film <- rownames(df_i) # add a new column with the same content of rownames
df_top_n <- as.data.frame(TOP_N_list_all_user[,i]) # top-n list of user-i
colnames(df_top_n) <- "Film"
df_cross <- inner_join(df_i, df_top_n, by="Film") # inner join the two dataset, we get the rated items in the top-n list
novelty <- 1 - dim(df_cross)[1]/N # novelty value of user-i
novelty_table <- rbind(novelty_table, novelty)
}
novelty_table$UserID <- rownames(mx)
colnames(novelty_table) <- c("novelty","UserID")
novelty_table <- novelty_table %>% select(UserID,novelty) # novelty table
### result of accuracy, coverage, and novelty
my_list <- list("accuracy" = acc_IBCF,"coverage" = coverage, "novelty" = novelty_table)
return(my_list)
}
test <- calc_topn_metrics(mx_reduced,0.8,20)
test$accuracy;test$coverage; test$novelty
TP FP FN TN N precision recall TPR FPR
[1,] 6.9 12.9875 77.075 583.0375 680 0.3460227 0.09009878 0.09009878 0.02159826
11 Implementierung Top-N Monitor Aufgabe DIY: Untersuche die relative Übereinstimmung zwischen Top-N Empfehlungen und präferierten Filmen für 4 unterschiedliche Modelle (z.B. IBCF und UBCF mit unterschiedlichen Ähnlichkeits-metriken / Nachbarschaften sowie SVD mit unterschiedlicher Dimensionalitätsreduktion).
11.1 Fixiere 20 zufällig gewählte Testkunden für alle Modellvergleiche,
set.seed(578)
train_test_11 <- evaluationScheme(rrm_reduced, method="split", train=0.95, k=1, given=20,goodRating=4)
# training dataset has 380 users,test dataset has 20 users
# given=20: For each test user, 20 films per user will be used for prediction, the rest for evaluation)
rrm_reduced_train_11 <- getData(train_test_11,"train")
rrm_reduced_known_11 <- getData(train_test_11,"known")
rrm_reduced_unknown_11 <- getData(train_test_11,"unknown")
# ICBF models
model_IBCF_cos_10 <-Recommender(data = rrm_reduced_train_11,method="IBCF",parameter=list(normalize = "Z-score",method="Cosine",k=10))
model_IBCF_cos_50 <-Recommender(data = rrm_reduced_train_11,method="IBCF",parameter=list(normalize = "Z-score",method="Cosine",k=50))
model_IBCF_ps_10 <-Recommender(data = rrm_reduced_train_11,method="IBCF",parameter=list(normalize = "Z-score",method="Pearson",k=10))
model_IBCF_ps_50 <-Recommender(data = rrm_reduced_train_11,method="IBCF",parameter=list(normalize = "Z-score",method="Pearson",k=50))
# UBCF models
model_UBCF_cos_10 <-Recommender(data = rrm_reduced_train_11,method="UBCF",parameter=list(normalize = "Z-score",method="Cosine",nn=10))
model_UBCF_cos_50 <-Recommender(data = rrm_reduced_train_11,method="UBCF",parameter=list(normalize = "Z-score",method="Cosine",nn=50))
model_UBCF_ps_10 <-Recommender(data = rrm_reduced_train_11,method="UBCF",parameter=list(normalize = "Z-score",method="Pearson",nn=10))
model_UBCF_ps_50 <-Recommender(data = rrm_reduced_train_11,method="UBCF",parameter=list(normalize = "Z-score",method="Pearson",nn=50))
# SVD models
model_SVD_10 <- Recommender(data = rrm_reduced_train_11,method="SVD",parameter=list(normalize = "Z-score",k=10))
model_SVD_50 <- Recommender(data = rrm_reduced_train_11,method="SVD",parameter=list(normalize = "Z-score",k=50))
# evaluation of the predictions
acc_IBCF_cos_10 <- calcPredictionAccuracy(predict(object = model_IBCF_cos_10, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_IBCF_cos_50 <- calcPredictionAccuracy(predict(object = model_IBCF_cos_50, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_IBCF_ps_10 <- calcPredictionAccuracy(predict(object = model_IBCF_ps_10, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_IBCF_ps_50 <- calcPredictionAccuracy(predict(object = model_IBCF_ps_50, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_UBCF_cos_10 <- calcPredictionAccuracy(predict(object = model_UBCF_cos_10, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_UBCF_cos_50 <- calcPredictionAccuracy(predict(object = model_UBCF_cos_50, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_UBCF_ps_10 <- calcPredictionAccuracy(predict(object = model_UBCF_ps_10, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_UBCF_ps_50 <- calcPredictionAccuracy(predict(object = model_UBCF_ps_50, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_SVD_10 <- calcPredictionAccuracy(predict(object = model_SVD_10, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_SVD_50 <- calcPredictionAccuracy(predict(object = model_SVD_50, newdata = rrm_reduced_known_11, n = 15,type="topNList"),rrm_reduced_unknown_11,given=20,goodRating = 4)
acc_table <- rbind(acc_IBCF_cos_10,acc_IBCF_cos_50,acc_IBCF_ps_10,acc_IBCF_ps_50,acc_UBCF_cos_10,acc_UBCF_cos_50,acc_UBCF_ps_10,acc_UBCF_ps_50,acc_SVD_10,acc_SVD_50)
acc_table
TP FP FN TN N precision recall TPR FPR
acc_IBCF_cos_10 6.30 8.70 87.15 577.85 680 0.4200000 0.07252980 0.07252980 0.01456784
acc_IBCF_cos_50 6.75 8.25 86.70 578.30 680 0.4500000 0.07716093 0.07716093 0.01370982
acc_IBCF_ps_10 3.10 11.15 90.35 575.40 680 0.2364881 0.03374307 0.03374307 0.01900455
acc_IBCF_ps_50 5.15 9.85 88.30 576.70 680 0.3433333 0.05386252 0.05386252 0.01642536
acc_UBCF_cos_10 2.85 12.15 90.60 574.40 680 0.1900000 0.03506794 0.03506794 0.02069613
acc_UBCF_cos_50 2.45 12.55 91.00 574.00 680 0.1633333 0.03580625 0.03580625 0.02140033
acc_UBCF_ps_10 2.30 12.70 91.15 573.85 680 0.1533333 0.02657352 0.02657352 0.02167117
acc_UBCF_ps_50 2.45 12.55 91.00 574.00 680 0.1633333 0.03007206 0.03007206 0.02136549
acc_SVD_10 6.95 8.05 86.50 578.50 680 0.4633333 0.07790237 0.07790237 0.01341930
acc_SVD_50 5.90 9.10 87.55 577.45 680 0.3933333 0.07229660 0.07229660 0.01537873
In the IBCF model, both precision and recall are better with cosine method and 50 neighbors.
In the UBCF model, cosine method and 10 neighbors is a better combination.
In the SVD model, precision and recall are better with singular value of 10.
Through all the models, The SVD model with singular value of 10 has the best precision (0.463) and recall (0.0779).
11.2 Bestimme den Anteil der Top-N Empfehlung nach Genres pro Kunde,
Top_n_genre <- function(Top_n_list,n){ # mx is user-item matrix; Top_n_list: top-n matrix; n: the "n" in top-n
table = data.frame()
for(i in 1:dim(Top_n_list)[2]){
df_top <- as.data.frame(Top_n_list[,i])
colnames(df_top) <- "Film"
df_film_genre_1 <- as.data.frame(mx_film_genre)
df_film_genre_1$Film <- rownames(df_film_genre_1)
df_top <- left_join(df_top,df_film_genre_1,by=("Film")) %>% select(-Film)
df_top <- df_top[-1,]
total <- sum(df_top)
df_top["ratio",] <- colSums(df_top)/total
df_top <- df_top["ratio",]
table <- rbind(table,df_top)
}
rownames(table) <- colnames(Top_n_list)
return(table)
}
# Top-15 recommendation list of SVD with k = 10
Pred_SVD_k10 <- predict(object = model_SVD_10, newdata = rrm_reduced_known_11, n = 15,type=c("topNList"))
Top15_SVD <- sapply(Pred_SVD_k10@items, function(x) {colnames(df_reduced)[x]})
Top_15_recommendations <- Top_n_genre(Top15_SVD,15) # the percentage of top-15 recommendations by genre per test user
Top_15_recommendations;summary(rowSums(Top_15_recommendations))[-4] # check if the total genre ratio for each user = 1
Min. 1st Qu. Median 3rd Qu. Max.
1 1 1 1 1
The table shows the percentage of genres in the top-15 recommendation list per user.
The sum of each row are all 1, this indicates the total ratio of each user are all correct.
11.3 Bestimme pro Kunde den Anteil nach Genres seiner Top-Filme (=Filme, welche vom Kunden die besten Bewertungen erhalten haben)
Top_film_genre <- function(mx,n){ # mx is user-item matrix, n: top-n rated films
table = data.frame()
for(i in 1:dim(mx)[1]){
df_top <- as.data.frame(t(mx))
df_top$Film <- rownames(df_top)
df_top <- df_top[,c(i,(dim(mx)[1]+1))]
colnames(df_top) <- c("Ratings","Film")
df_top <- df_top %>% filter(complete.cases(.)) %>% arrange(desc(Ratings)) %>% slice(1:n)
df_film_genre_1 <- as.data.frame(mx_film_genre)
df_film_genre_1$Film <- rownames(df_film_genre_1)
df_left_join <- left_join(df_top,df_film_genre_1,by=("Film"))
df_top <- df_left_join[,-(1:2)]
total <- sum(df_top)
df_top["ratio",] <- colSums(df_top)/total
df_top <- df_top["ratio",]
table <- rbind(table,df_top)
}
rownames(table) <- rownames(mx)
return(table)
}
Top_15_films <- Top_film_genre(mx_reduced,15) # genres proportion of the top 15 films for every user
Top_15_films
summary(rowSums(Top_15_films))[-4]
Min. 1st Qu. Median 3rd Qu. Max.
1 1 1 1 1
The first table shows the percentage of genres in the top-15 rated list per user.
The sum of each row are all 1, this indicates the total ratio of each user are all correct.
11.4 Vergleiche pro Kunde Top-Empfehlungen und Top-Filmen nach Genres,
# filter the Top-Filmen with the users only appear in the Top-recommendation
Top_15_films_reduced <- Top_15_films
Top_15_films_reduced$UserID <- rownames(Top_15_films_reduced)
Top_15_films_reduced <- Top_15_films_reduced %>% filter(UserID %in% rownames(Top_15_recommendations)) %>% select(-UserID) # with 20 users
# calculate the mean absolute error
MAE_top_genre <- rowSums(abs(Top_15_films_reduced - Top_15_recommendations))/20
"MAE between Top-recommendations and Top-films by genres per user:"; MAE_top_genre;"the five number statistics of the MAE:";summary(MAE_top_genre)[-4]
[1] "MAE between Top-recommendations and Top-films by genres per user:"
393 417 279 474 472 379 823 267 577 536
0.03677885 0.02048067 0.02954545 0.04768892 0.02958937 0.02647059 0.02817204 0.03555556 0.03646552 0.04252252
899 484 361 391 901 215 323 918 828 552
0.03333333 0.02379032 0.04028122 0.03775388 0.02978177 0.04346591 0.03600000 0.03081897 0.04404894 0.02547093
[1] "the five number statistics of the MAE:"
Min. 1st Qu. Median 3rd Qu. Max.
0.02048067 0.02920210 0.03444444 0.03838572 0.04768892
"MSE between Top-recommendations and Top-films by genres per user:"
[1] "MSE between Top-recommendations and Top-films by genres per user:"
MSE_top_genre <- rowSums((Top_15_films_reduced - Top_15_recommendations)^2)/20
MSE_top_genre;"the five number statistics of the MSE:";summary(MSE_top_genre)[-4]
393 417 279 474 472 379 823 267 577 536
0.003692125 0.001040455 0.002926997 0.006015010 0.002028927 0.002454184 0.001581634 0.002370370 0.002941290 0.004354336
899 484 361 391 901 215 323 918 828 552
0.002295684 0.001557035 0.004265842 0.003357985 0.002117153 0.003690761 0.003457500 0.002399952 0.006203655 0.001318853
[1] "the five number statistics of the MSE:"
Min. 1st Qu. Median 3rd Qu. Max.
0.001040455 0.002095096 0.002690591 0.003691102 0.006203655
"RMSE between Top-recommendations and Top-films by genres per user:"
[1] "RMSE between Top-recommendations and Top-films by genres per user:"
RMSE_top_genre <- sqrt(rowSums((Top_15_films_reduced - Top_15_recommendations)^2)/20)
RMSE_top_genre;"the five number statistics of the RMSE:";summary(RMSE_top_genre)[-4]
393 417 279 474 472 379 823 267 577 536
0.06076286 0.03225609 0.05410173 0.07755650 0.04504361 0.04953972 0.03976977 0.04868645 0.05423366 0.06598740
899 484 361 391 901 215 323 918 828 552
0.04791330 0.03945928 0.06531341 0.05794812 0.04601253 0.06075163 0.05880051 0.04898930 0.07876328 0.03631601
[1] "the five number statistics of the RMSE:"
Min. 1st Qu. Median 3rd Qu. Max.
0.03225609 0.04577030 0.05182073 0.06075444 0.07876328
Three quantitativ metrics MAE(mean average error), MSE(mean squared error), RMSE(the root mean squared error) were used to compare the difference between the top-recommendations and top-rated-films by genres.
11.5 Definiere eine Qualitätsmetrik für Top-N Listen und teste sie.
# MAP: Average Precision and Mean Average Precision
MAP <- function(mx,Top_n_list,n){
# extract the users in the Top-n lists, or use direct the test dataset.
mx_part <- as.data.frame(mx) %>% filter(rownames(as.data.frame(mx)) %in% colnames(as.data.frame(Top_n_list)))# user_film
mx_part <- as.data.frame(t(mx_part)) # transpose mx_part_users to film_user
mx_part$Film <- rownames(mx_part) # generate new column "Film" same as the rownames
Top_n_list <- as.data.frame(Top_n_list)
Top_n_list$Rank <- 1:n # generate new column "Rank" to represent the ranks of the recommended films
summe_precision <- 0
for(i in (dim(mx_part)[2]-1)){
Top_i <- Top_n_list[,c(all_of(i),dim(Top_n_list)[2])] # extract the top_n_list and rank of the i-th user
colnames(Top_i) <- c("Film","Rank") # rename the columns as "Film" and "Rank"
mx_i <- mx_part %>% select(c(all_of(i),dim(mx_part)[2])) # mx_i: extract the ratings and Film names of i-th user from rating matrix
colnames(mx_i) <- c("Rating","Film")
mx_join <- left_join(Top_i,mx_i,by="Film") %>% filter(Rating>3) # left_join the ratings to the Top-n list by "Film". mx_1 has the columns of "Film", "Rank", and ratings; filter the relevant items (ratings greater than 3);
mx_join <- mx_join %>% mutate(Numerator = 1:dim(mx_join)[1],Precision = Numerator/Rank) # generate new column "Numerator" which is a new rank only for the relevant items, and new column "Precision" which is the Precision of every relevant items.
avg_user_i_precision <- mean(mx_join$Precision) # average precision of user-i
summe_precision <- summe_precision + avg_user_i_precision
}
map <- summe_precision/(dim(Top_n_list)[2]-1) # mean average precision
return(map)
}
MAP(mx_reduced,TOP15_IBCF,15)
[1] 0.008875812
firstly, for one user, find out the rank of the m-th relevant item (rating > 3) in the top_n_list, then calculate the precision: m/n.
secondly, calculate the precisions of all relevant items.
the average precision of one user: average all the precision of relevant items.
MAP: average precision of all users.
LS0tDQp0aXRsZTogIkNvbGxhYm9yYXRpdmUgTW92aWUgUmVjb21tZW5kZXIiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCmVkaXRvcl9vcHRpb25zOiANCiAgbWFya2Rvd246IA0KICAgIHdyYXA6IDcyDQotLS0NCg0KMS4gIExpYnJhcnkgdW5kIERhdGENCg0KYGBge3J9DQpsaWJyYXJ5KHRpZHl2ZXJzZSkNCmxpYnJhcnkoZHBseXIpDQpsaWJyYXJ5KGRhdGEudGFibGUpDQpsaWJyYXJ5KGdncGxvdDIpDQpsaWJyYXJ5KHJlc2hhcGUyKQ0KbGlicmFyeShyc2FtcGxlKQ0KbGlicmFyeShyZWNvbW1lbmRlcmxhYikNCmRhdGEoTW92aWVMZW5zZSkNCmBgYA0KDQoyLiAgRXhwbG9yYXRpdmUgRGF0ZW5hbmFseXNlDQoNCmBgYHtyfQ0KbXhfdXNlcl9maWxtIDwtIGFzKE1vdmllTGVuc2UsICJtYXRyaXgiKSAgIyBjb252ZXJ0IHJlYWxyYXRpbmdtYXRyaXggdG8gbm9ybWFsIG1hdHJpeA0KZGZfdXNlcl9maWxtIDwtIGFzLmRhdGEuZnJhbWUobXhfdXNlcl9maWxtKSAgICMgIGNvbnZlcnQgbWF0cml4IHRvIGRhdGFmcmFtZSBmb3JtDQpkZl9maWxtX3VzZXIgPC0gYXMuZGF0YS5mcmFtZSh0KG14X3VzZXJfZmlsbSkpICMgdHJhbnNwb3NlIHRoZSBkYXRhZnJhbWU6IGVhY2ggcm93IGlzIGEgbW92aWUgbmFtZSwgZWFjaCBjb2x1bW4gaXMgYSB1c2VyDQpgYGANCg0KMi4xIFdlbGNoZXMgc2luZCBkaWUgYW0gaMOkdWZpZ3N0ZW4gZ2VzY2hhdXRlbiBHZW5yZXMvRmlsbWU/DQoNCmBgYHtyfQ0KZGZfMjEgPC0gZGZfZmlsbV91c2VyICU+JSBtdXRhdGUoY250ID0gcm93U3VtcyghaXMubmEoZGZfZmlsbV91c2VyKSkpICU+JSBhcnJhbmdlKGRlc2MoY250KSkgJT4lIGZpbHRlcihjbnQgPT0gbWF4KGNudCkpICU+JSBzZWxlY3QoJ2NudCcpDQpkZl8yMQ0KYGBgDQojIyMgRGllIGFtIGjDpHVmaWdzdGVuIGdlc2NoYXV0ZW4gRmlsbWUgaXN0IFN0YXIgV2Fycy4NCg0KMi4yIFdpZSB2ZXJ0ZWlsZW4gc2ljaCBkaWUgS3VuZGVucmF0aW5ncyBnZXNhbXRoYWZ0IHVuZCBuYWNoIEdlbnJlcz8NCg0KYGBge3J9DQpkZl91bmxpc3QgPC0gZGF0YS5mcmFtZShyYXRpbmc9dW5saXN0KGRmX2ZpbG1fdXNlcikpICAgICAgICAgICAgIyB1bmxpc3QgdGhlIGRhdGFmcmFtZQ0KZ2dwbG90KGRmX3VubGlzdCxhZXMocmF0aW5nKSkgKyBnZW9tX2hpc3RvZ3JhbSgpICsgICAgICAgICAgICAgICAgIyBkaWUgVmVydGVpbHVuZyBkZXIgS3VuZGVucmF0aW5ncyBnZXNhbXRoYWZ0DQogIGxhYnMoeD0iUmF0aW5ncyIsIHk9IkNvdW50Iix0aXRsZT0iRGlzdHJpYnV0aW9uIG9mIHRoZSB1c2VyIHJhdGluZ3MiKSArDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQ0KYGBgDQojIyMgVGhlIGFib3ZlIGhpc3RvZ3JhbSBvZiByYXRpbmdzIGRpc3RyaWJ1dGlvbiBpcyBsZWZ0IHNrZXdlZCwgd2l0aCB0aGUgbW9kZSA9IDQuDQoNCg0KYGBge3J9DQpteF9maWxtX2dlbnJlIDwtIGFzLmRhdGEuZnJhbWUoTW92aWVMZW5zZU1ldGEpIA0Kcm93bmFtZXMobXhfZmlsbV9nZW5yZSkgPC0gbXhfZmlsbV9nZW5yZSR0aXRsZQ0KbXhfZmlsbV9nZW5yZSA8LSBhcy5tYXRyaXgobXhfZmlsbV9nZW5yZVssNToyMl0pICAgIyBNb3ZpZSBHZW5yZSBNYXRyaXgNCg0KbXhfdXNlcl9maWxtW2lzLm5hKG14X3VzZXJfZmlsbSldIDwtIDANCg0KbXhfdXNlcl9nZW5yZSA8LSBteF91c2VyX2ZpbG0gJSolIG14X2ZpbG1fZ2VucmUNCg0KbXhfZ2VucmVfdXNlciA8LSBhcy5kYXRhLmZyYW1lKHQobXhfdXNlcl9nZW5yZSkpICAgICMgYTogU3TDpHJrZSBHZW5yZSBLb21iaW5hdGlvbiB2b2xsc3TDpG5kaWcNCm14X2dlbnJlX3VzZXIkc3VtbWUgPC0gcm93U3VtcyhteF9nZW5yZV91c2VyKSAgICAgICAgICAgICAgICMgbmV3IGNvbHVtbiAic3VtbWUiOiBzdW1tZSB1c2VyIHJhdGluZ3Mgb2YgZWFjaCBnZW5yZQ0KbXhfZ2VucmVfdXNlciA8LSBjYmluZChnZW5yZSA9IHJvd25hbWVzKG14X2dlbnJlX3VzZXIpLCBteF9nZW5yZV91c2VyKSMgbmV3IGNvbHVtbiAiZ2VucmUiOiBnZW5yZSBuYW1lIGNvcGllZCBmcm9tIHJvd25hbWVzDQpnZ3Bsb3QobXhfZ2VucmVfdXNlcixhZXMoc3VtbWUsZ2VucmUpKSArIGdlb21fY29sKCkgKyBsYWJzKHg9ICJzdW1tZWQgcmF0aW5ncyBvZiBhbGwgdXNlcnMiLCB5PSJHZW5yZSIsdGl0bGU9IkRpc3RyaWJ1dGlvbiBvZiB0aGUgdXNlciByYXRpbmdzIGJ5IGdlbnJlIGNvbWJpbmF0aW9uIikgKyANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpteF9nZW5yZV91c2VyIDwtIG14X2dlbnJlX3VzZXIgJT4lIHNlbGVjdCgtZ2VucmUpDQpgYGANCiMjIyBBYm92ZSBpcyB0aGUgZGlzdHJpYnV0aW9uIG9mIHJhdGluZ3MgYnkgZ2VucmUsICJkcmFtYSIgaGFzIHRoZSBoaWdoZXN0IHN1bW1lZCByYXRpbmdzLg0KDQpgYGB7cn0NCmRmXzIyIDwtIGFzLmRhdGEuZnJhbWUodChteF9maWxtX2dlbnJlKSkgJT4lIG11dGF0ZShjbnQgPSByb3dTdW1zKGFzLmRhdGEuZnJhbWUodChteF9maWxtX2dlbnJlKSkpKSU+JSBhcnJhbmdlKGRlc2MoY250KSkgICMgYWRkIG5ldyBjb2x1bW46IGNvdW50IGZvciBlYWNoIGdlbnJlcw0KZGZfMjIgPC0gY2JpbmQoZ2VucmVzID0gcm93bmFtZXMoZGZfMjIpLGRmXzIyKSAgICAgICAgICAgICAgICMgaW5kZXggYXMgYSBjb2x1bW4NCnJvd25hbWVzKGRmXzIyKSA8LSAxOm5yb3coZGZfMjIpICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgZ2VuZXJhdGUgbmV3IGluZGV4DQoNCmdncGxvdChkZl8yMixhZXMoeCA9IChyZW9yZGVyKGdlbnJlcyxjbnQpKSwgeSA9IGNudCkpICsgZ2VvbV9jb2woKSArIGNvb3JkX2ZsaXAoKSArDQogIGxhYnMoeT0iTnVtYmVyIG9mIFZpZXdzIiwgeD0iR2VucmVzIix0aXRsZT0iRGlzdHJpYnV0aW9uIGJ5IGdlbnJlcyIpICsgDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQ0KYGBgDQojIyMgVGhlIHBsb3QgYWJvdmUgc2hvd3MgdGhlIGRpc3RyaWJ1dGlvbiBvZiB2aWV3cyBieSBnZW5yZS4gVGhlIGdlbnJlIGRyYW1hIGhhcyB0aGUgaGlnaGVzdCBudW1iZXIgb2Ygdmlld3MuDQoNCjIuMyBXaWUgdmVydGVpbGVuIHNpY2ggZGllIG1pdHRsZXJlbiBLdW5kZW5yYXRpbmdzIHBybyBGaWxtPw0KDQpgYGB7cn0NCmRmX2F2Z19yYXRpbmdfZmlsbSA8LSBkZl9maWxtX3VzZXIgJT4lIG11dGF0ZShhdmdfcmF0aW5nID0gcm93TWVhbnMoZGZfZmlsbV91c2VyLG5hLnJtID0gVFJVRSwgZGltcyA9IDEpKSAlPiUgc2VsZWN0KCdhdmdfcmF0aW5nJykNCmdncGxvdChkZl9hdmdfcmF0aW5nX2ZpbG0sYWVzKGF2Z19yYXRpbmcpKSArIGdlb21faGlzdG9ncmFtKGJpbndpZHRoID0gMSkgKyAgICAgICAgICAgICAgICAjIGRpZSBWZXJ0ZWlsdW5nDQogIGxhYnMoeD0iTWVhbiB1c2VyLXJhdGluZ3MgcGVyIGZpbG0iLCB5PSJDb3VudCBvZiBmaWxtcyIsdGl0bGU9IkRpc3RyaWJ1dGlvbiBvZiB0aGUgbWVhbiB1c2VyLXJhdGluZ3MgcGVyIGZpbG0iKSArIA0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkNCg0KYGBgDQojIyMgVGhlIHBsb3Qgc2hvd2VkIHVzIHRoYXQgdGhlIG1vZGUgb2YgYXZlcmFnZSByYXRpbmdzIHBlciBmaWxtIGlzIDMuIE1vc3Qgb2YgbW92aWVzIGhhdmUgdGhlIGF2ZXJhZ2UgcmF0aW5nIGxhcmdlciB0aGFuIDIuIA0KDQoNCjIuNCBXaWUgc3Rhcmsgc3RyZXVlbiBkaWUgUmF0aW5ncyB2b24gaW5kaXZpZHVlbGxlbiBLdW5kZW4/DQoNCmBgYHtyfQ0KZGZfYXZnX3JhdGluZ191c2VyIDwtIGRmX3VzZXJfZmlsbSAlPiUgbXV0YXRlKGF2Z19yYXRpbmcgPSByb3dNZWFucyhkZl91c2VyX2ZpbG0sbmEucm0gPSBUUlVFLCBkaW1zID0gMSkpICU+JSBzZWxlY3QoJ2F2Z19yYXRpbmcnKQ0KZ2dwbG90KGRmX2F2Z19yYXRpbmdfdXNlcixhZXMoYXZnX3JhdGluZykpICsgZ2VvbV9oaXN0b2dyYW0oYmlucyA9IDUpICsgICAgICAgICAgICAgICAgIyBkaWUgVmVydGVpbHVuZw0KICBsYWJzKHg9Ik1lYW4gdXNlci1yYXRpbmdzIHBlciB1c2VyIiwgeT0iQ291bnQgb2YgdXNlcnMiLHRpdGxlPSJEaXN0cmlidXRpb24gb2YgdGhlIG1lYW4gdXNlci1yYXRpbmdzIHBlciB1c2VyIikrIA0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkNCmBgYA0KIyMjIFRoZSBwbG90IHNob3dzIHRoZSBtb2RlIG9mIGF2ZXJhZ2UgdXNlciByYXRpbmdzIHBlciB1c2VyIGlzIDMuIE1vc3Qgb2YgdGhlIGF2ZXJhZ2UgcmF0aW5ncyBhcmUgMyBvciA0Lg0KDQoNCjIuNSBXZWxjaGVuIEVpbmZsdXNzIGhhdCBkaWUgTm9ybWllcnVuZyBkZXIgUmF0aW5ncyBwcm8gS3VuZGUgYXVmIGRlcmVuIFZlcnRlaWx1bmc/DQpgYGB7cn0NCmRmX2F2Z19yYXRpbmdfdXNlciA8LSBkZl91c2VyX2ZpbG0gJT4lIG11dGF0ZShhdmdfcmF0aW5nID0gcm93TWVhbnMoZGZfdXNlcl9maWxtLG5hLnJtID0gVFJVRSwgZGltcyA9IDEpKSAlPiUgc2VsZWN0KCdhdmdfcmF0aW5nJykNCmdncGxvdChkZl9hdmdfcmF0aW5nX3VzZXIsYWVzKGF2Z19yYXRpbmcpKSArIGdlb21faGlzdG9ncmFtKGJpbnMgPSAyMCkgKyAgICAgICAgICAgICAgICAjIGRpZSBWZXJ0ZWlsdW5nDQogIGxhYnMoeD0iTWVhbiByYXRpbmdzIHBlciB1c2VyIiwgeT0iQ291bnQgb2YgdXNlcnMiLHRpdGxlPSJEaXN0cmlidXRpb24gb2YgdGhlIG1lYW4gcmF0aW5ncyBwZXIgdXNlciIpKyANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpgYGANCg0KYGBge3J9DQpub3JtYWxpemVkX21vdmllbGVucyA8LSBhcyhub3JtYWxpemUoTW92aWVMZW5zZSxtZXRob2QgPSAiei1zY29yZSIpLCAibWF0cml4IikNCm5vcm1hbGl6ZWRfbW92aWVsZW5zIDwtIGFzLmRhdGEuZnJhbWUobm9ybWFsaXplZF9tb3ZpZWxlbnMpDQpub3JtYWxpemVkX2F2Z19yYXRpbmdfdXNlciA8LSBub3JtYWxpemVkX21vdmllbGVucyAlPiUgbXV0YXRlKGF2Z19yYXRpbmc9cm93TWVhbnMobm9ybWFsaXplZF9tb3ZpZWxlbnMsbmEucm09VFJVRSwgZGltcz0xKSkgJT4lIHNlbGVjdCgnYXZnX3JhdGluZycpICANCg0KZ2dwbG90KG5vcm1hbGl6ZWRfYXZnX3JhdGluZ191c2VyLGFlcyhhdmdfcmF0aW5nKSkgKyBnZW9tX2hpc3RvZ3JhbShiaW5zID0gMjApICsgICAgICAgICAgICAgICAgIyBkaWUgVmVydGVpbHVuZw0KICBsYWJzKHg9Ik1lYW4gbm9ybWFsaXplZCByYXRpbmdzIHBlciB1c2VyIiwgeT0iQ291bnQgb2YgdXNlcnMiLHRpdGxlPSJEaXN0cmlidXRpb24gb2YgdGhlIG1lYW4gbm9ybWFsaXplZCByYXRpbmdzIHBlciB1c2VyIikgKyANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpgYGANCiMjIyB3aXRob3V0IG5vcm1hbGl6YXRpb24gKGZpcnN0IHBsb3QpOiB0aGUgYXZlcmFnZSByYXRpbmdzIGFyZSBzbGlnaHRseSBsZWZ0IHNrZXdlZCwgd2l0aCB0aGUgbW9kZSBvZiAzLjguIFRoZSByYXRpbmdzIHZhcnkgYSBsb3QgYWNyb3NzIGRpZmZlcmVudCB1c2Vycy4NCg0KIyMjIHdpdGggWi1zY29yZSBub3JtYWxpemF0aW9uIChzZWNvbmQgcGxvdCk6IHRoZSBhdmVyYWdlIHJhdGluZ3MgcGVyIHVzZXIgYXJlIGFsbCBhcm91bmQgMC4gVGhpcyBtZWFuLCB0aGUgcmF0aW5ncyBmcm9tIGRpZmZlcmVudCB1c2VycyBhcmUgbm9ybWFsaXplZCB0byB0aGUgc2FtZSBzY2FsZSwgd2l0aCB0aGUgbWVhbiBvZiAwLCB0aGUgc3RhbmRhcmQgZGV2aWF0aW9uIG9mIDEuIFRoaXMgd2lsbCByZWR1Y2UgdGhlIGluZmx1ZW5jZSBvZiByYXRpbmcgaGFiaXRzIG9mIGRpZmZlcmVudCB1c2Vycy4gDQoNCjIuNiBXZWxjaGUgc3RydWt0dXJlbGxlbiBDaGFyYWt0ZXJpc3Rpa2EgKHouQi4gU3BhcnNpdHkpIHVuZCBBdWZmw6RsbGlna2VpdGVuIHplaWd0IGRpZSBVc2VyLUl0ZW0gTWF0cml4Pw0KDQojIyMgUmVjb21tZW5kZXIgU3lzdGVtIGRhdGEgdXN1YWxseSBjb250YWlucyBhIGxhcmdlIG51bWJlcnMgb2YgdXNlcnMocm93cykgYW5kIGl0ZW1zIChjb2x1bW5zKSwgYnV0IGEgc2luZ2xlIHVzZXIgaW50ZXJhY3RzIHdpdGggb25seSBhIHNtYWxsIHN1YnNldCBvZiB0aGUgaXRlbXMuIFRoaXMgbWVhbnMsIHRoZSBkYXRhZnJhbWUgY29uc2lzdHMgb2YgbWFueSB6ZXJvIHZhbHVlcywgdGhlIHN0cnVjdHVyZSBpcyBleHRyZW1lbHkgc3BhcnNlLg0KDQojIyMgVGhlIFVzZXItSXRlbSBNYXRyaXggb2YgTW92aWVMZW5zZSBkYXRhc2V0IGlzIGRnQ01hdHJpeCwgd2hpY2ggaXMgYSBjbGFzcyBvZiBzcGFyc2UgbnVtZXJpYyBtYXRyaWNlcyBpbiB0aGUgY29tcHJlc3NlZCwgc3BhcnNlLCBjb2x1bW4tb3JpZW50ZWQgZm9ybWF0LiBJbiB0aGlzIGltcGxlbWVudGF0aW9uIHRoZSBub24temVybyBlbGVtZW50cyBpbiB0aGUgY29sdW1ucyBhcmUgc29ydGVkIGludG8gaW5jcmVhc2luZyByb3cgb3JkZXIuDQoNCg0KMyBEYXRlbnJlZHVrdGlvbg0KDQozLjEgUmVkdXppZXJlIGRlbiBNb3ZpZUxlbnNlIERhdGVuc2F0eiBhdWYgcnVuZCA0MDAgS3VuZGVuIHVuZCA3MDAgRmlsbWUsIGluZGVtIGR1IEZpbG1lIHVuZCBLdW5kZW4gbWl0IHNlaHIgd2VuaWdlbiBSYXRpbmdzIGVudGZlcm5zdC4NCg0KYGBge3J9DQpkZl9yZWR1Y2VkIDwtIGRmX2ZpbG1fdXNlciAlPiUgbXV0YXRlKG5fcHJvX2ZpbG0gPSByb3dTdW1zKCFpcy5uYShkZl9maWxtX3VzZXIpKSkgJT4lIGFycmFuZ2UoZGVzYyhuX3Byb19maWxtKSkgJT4lIHNsaWNlKDA6NzAwKSU+JSBzZWxlY3QoLW5fcHJvX2ZpbG0pICAgICAgICMgcmVkdWNlIHRvIDcwMCBtb3ZpZXMNCmRmX3JlZHVjZWQgPC0gYXMuZGF0YS5mcmFtZSh0KGRmX3JlZHVjZWQpKSANCmRmX3JlZHVjZWQgPC0gZGZfcmVkdWNlZCAlPiUgbXV0YXRlKG5fcHJvX3VzZXIgPSByb3dTdW1zKCFpcy5uYShkZl9yZWR1Y2VkKSkpICU+JSBhcnJhbmdlKGRlc2Mobl9wcm9fdXNlcikpICU+JSBzbGljZSgwOjQwMCkgJT4lIHNlbGVjdCgtbl9wcm9fdXNlcikgICMgcmVkdWNlIHRvIDQwMCB1c2Vycw0KZGZfcmVkdWNlZCAgICMgd2l0aCA0MDAgdXNlcnMgYW5kIDcwMCBmaWxtcy4NCmBgYA0KDQozLjIgVW50ZXJzdWNoZSB1bmQgZG9rdW1lbnRpZXJlIGRpZSBFaWdlbnNjaGFmdGVuIGRlcyByZWR1emllcnRlbiBEYXRlbnNhdHplcyB1bmQgYmVzY2hyZWliZSBkZW4gRWZmZWt0IGRlciBEYXRlbnJlZHVrdGlvbjogQW56YWhsIEZpbG1lIHVuZCBLdW5kZW4gc293aWUgU3BhcnNpdHkgdm9yIHVuZCBuYWNoIERhdGVucmVkdWt0aW9uDQoNCiMjIyBWb3IgRGF0ZW5yZWR1a3Rpb246IDE2NjQgTW92aWVzLCA5NDMgdXNlcnMsIDkzLjgyJSBEYXRhIGFyZSBOQS4NCmBgYHtyfQ0KcHJpbnQoZGltKGRmX3VzZXJfZmlsbSkpDQpwcmludChzdW0oaXMubmEoZGZfdXNlcl9maWxtKSkvKDE2NjMqOTQyKSkNCmBgYA0KYGBge3J9DQppbWFnZShhcyhkZl91c2VyX2ZpbG0sIm1hdHJpeCIpLCBtYWluID0gInNwYXJzaXR5IG9mIGRhdGFmcmFtZSBiZWZvcmUgcmVkdWN0aW9uIikNCmBgYA0KIyMjIE5hY2ggRGF0ZW5yZWR1a3Rpb246IDcwMCBNb3ZpZXMsIDQwMCB1c2VycywgNzUuOTAlIGRhdGEgYXJlIE5BLg0KDQpgYGB7cn0NCnByaW50KGRpbShkZl9yZWR1Y2VkKSkNCnByaW50KHN1bShpcy5uYShkZl9yZWR1Y2VkKSkvKDcwMCo0MDApKQ0KYGBgDQoNCmBgYHtyfQ0KaW1hZ2UoYXMoZGZfcmVkdWNlZCwibWF0cml4IiksbWFpbiA9ICJzcGFyc2l0eSBvZiBkYXRhZnJhbWUgYWZ0ZXIgcmVkdWN0aW9uIikNCmBgYA0KIyMjIFRoZSB0d28gaW1hZ2VzIGFib3ZlIHNob3dlZCB1cyB0aGUgZGF0YSBzcGFyc2l0eSBiZWZvcmUgKGZpcnN0IGltYWdlKSBhbmQgYWZ0ZXIgKHNlY29uZCBpbWFnZSkgcmVkdWN0aW9uLiBUaGUgYmxhbmsgcGl4ZWxzIHJlcHJlc2VudCB0aGUgTkEsIHRoZSBjb2xvciBwaXhlbHMgcmVwcmVzZW50IHRoZSBhdmFpbGFibGUgdmFsdWVzLiBCeSBjb21wYXJpbmcgdGhlIHR3byBpbWFnZXMsIHdlIGNvdWxkIHNlZSB0aGF0IHRoZSBmaXJzdCBpbWFnZSBoYXMgbW9yZSBibGFuayBhbmQgbGVzcyBjb2xvciBwaXhlbHMgdGhhbiB0aGUgc2Vjb25kIG9uZS4gVGhpcyBtZWFucyB0aGUgZGF0YSBhZnRlciByZWR1Y3Rpb24gaXMgbGVzcyBzcGFyc2UgdGhhbiBiZWZvcmUgcmVkdWN0aW9uLiBEYXRhIHJlZHVjdGlvbiBoYXMgc3VjY2Vzc2Z1bGx5IHJlZHVjZWQgdGhlIGRhdGEgc3BhcnNpdHkuDQoNCg0KDQozLjMgbWl0dGxlcmUgS3VuZGVucmF0aW5ncyBwcm8gRmlsbSB2b3IgdW5kIG5hY2ggRGF0ZW5yZWR1a3Rpb24uDQoNCiMjIyBCZWZvcmUgZGF0YSByZWR1Y3Rpb24NCg0KYGBge3J9DQpkZl9hdmdfcmF0aW5nIDwtIGRmX2ZpbG1fdXNlciAlPiUgbXV0YXRlKGF2Z19yYXRpbmcgPSByb3dNZWFucyhkZl9maWxtX3VzZXIsbmEucm0gPSBUUlVFLCBkaW1zID0gMSkpICU+JSBzZWxlY3QoJ2F2Z19yYXRpbmcnKQ0KZ2dwbG90KGRmX2F2Z19yYXRpbmcsYWVzKGF2Z19yYXRpbmcpKSArIGdlb21faGlzdG9ncmFtKGJpbndpZHRoID0gMC4yNSkgKyAgICAgICAgICAgICAgICAjIGRpZSBWZXJ0ZWlsdW5nDQogIGxhYnMoeD0iTWVhbiByYXRpbmdzIHBlciBmaWxtIiwgeT0iQ291bnQiLHRpdGxlPSJCZWZvcmUgcmVkdWN0aW9uOiBEaXN0cmlidXRpb24gb2YgdGhlIG1lYW4gcmF0aW5ncyBieSBmaWxtIikgKyANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpgYGANCg0KYGBge3J9DQpkZl9yZWR1Y2VkX3QgPC0gYXMuZGF0YS5mcmFtZSh0KGRmX3JlZHVjZWQpKQ0KZGZfcmVkdWNlZF9hdmdfcmF0aW5nIDwtIGRmX3JlZHVjZWRfdCU+JSBtdXRhdGUoYXZnX3JhdGluZyA9IHJvd01lYW5zKGRmX3JlZHVjZWRfdCxuYS5ybSA9IFRSVUUsIGRpbXMgPSAxKSkgJT4lIHNlbGVjdCgnYXZnX3JhdGluZycpDQpnZ3Bsb3QoZGZfcmVkdWNlZF9hdmdfcmF0aW5nLGFlcyhhdmdfcmF0aW5nKSkgKyBnZW9tX2hpc3RvZ3JhbShiaW53aWR0aCA9IDAuMjUpICsgICAgICAgICAgICAgICAgIyBkaWUgVmVydGVpbHVuZw0KICBsYWJzKHg9Ik1lYW4gcmF0aW5ncyBwZXIgZmlsbSIsIHk9IkNvdW50Iix0aXRsZT0iQWZ0ZXIgcmVkdWN0aW9uOiBEaXN0cmlidXRpb24gb2YgdGhlIG1lYW4gcmF0aW5ncyBieSBmaWxtIikgKyANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpgYGANCiMjIyBBZnRlciB0aGUgZGF0YSByZWR1Y3Rpb24sIHRoZSBhdmVyYWdlIHJhdGluZ3MgYXJlIGNsb3NlIHRvIGEgbGVmdCBza2V3ZWQgbm9ybWFsIGRpc3RyaWJ1dGlvbi4NCg0KDQoNCg0KNCBBbmFseXNlIMOEaG5saWNoa2VpdHNtYXRyaXgNCg0KNC4xIFplcmxlZ2UgZGVuIHJlZHV6aWVydGVuIE1vdmllTGVuc2UgRGF0ZW5zYXR6IGluIGVpbiBkaXNqdW5rdGUgVHJhaW5pbmdzLXVuZCBUZXN0ZGF0ZW5zZXQgaW0gVmVyaMOkbHRuaXMgNDoxDQoNCmBgYHtyfQ0Kc2V0LnNlZWQoNDY1KQ0KbXhfcmVkdWNlZCA8LSBhcy5tYXRyaXgoZGZfcmVkdWNlZCkNCnJybV9yZWR1Y2VkIDwtIGFzKG14X3JlZHVjZWQsInJlYWxSYXRpbmdNYXRyaXgiKQ0KdHJhaW5fdGVzdCA8LSBldmFsdWF0aW9uU2NoZW1lKHJybV9yZWR1Y2VkLCBtZXRob2Q9InNwbGl0IiwgdHJhaW49MC44LCBrPTEsIGdpdmVuPTIwLCBnb29kUmF0aW5nPTQpDQoNCiMgdHJhaW5pbmcgZGF0YSA4MCUgb2YgdGhlIHVzZXJzDQpycm1fcmVkdWNlZF90cmFpbiA8LSBnZXREYXRhKHRyYWluX3Rlc3QsInRyYWluIikNCg0KDQojIHRlc3QgZGF0YSBpcyAyMCUgb2YgdGhlIGFsbCB1c2VycywgdGhlIHRlc3QgZGF0YSBpcyBzcGxpdGVkIGludG8gdHdvIHBhcnRzOiBrbm93biB0ZXN0IGRhdGEgYW5kIHVua25vd24gdGVzdCBkYXRhDQoNCiMgdGhlIGtub3duIHBvcnRpb24gcmV0dXJucyBzcGVjaWZpZWQgMjAgaXRlbXMgcGVyIHRlc3QgdXNlciBpcyB1c2VkIHRvIHByZWRpY3QgcmF0aW5ncyBvciBmaWxtcyBmb3IgdGhlIHRlc3QgdXNlcnMNCnJybV9yZWR1Y2VkX2tub3duIDwtIGdldERhdGEodHJhaW5fdGVzdCwia25vd24iKQ0KDQoNCiMgdGhlIHVua25vd24gcG9ydGlvbiBpcyB1c2VkIHRvIGNvbXB1dGUgdGhlIHByZWRpY3Rpb24gZXJyb3Igb2YgdGhlIG1vZGVsDQpycm1fcmVkdWNlZF91bmtub3duIDwtIGdldERhdGEodHJhaW5fdGVzdCwidW5rbm93biIpDQoNCmBgYA0KDQo0LjIgVHJhaW5pZXJlIGVpbiBJQkNGIE1vZGVsbCBtaXQgMzAgTmFjaGJhcm4gdW5kIENvc2luZSBTaW1pbGFyaXR5DQoNCmBgYHtyfQ0KbW9kZWxfSUJDRiA8LSBSZWNvbW1lbmRlcihkYXRhID0gcnJtX3JlZHVjZWRfdHJhaW4sbWV0aG9kPSJJQkNGIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsbWV0aG9kPSJDb3NpbmUiLGs9MzApKSANCg0KYGBgDQoNCjQuMyBCZXN0aW1tZSBkaWUgVmVydGVpbHVuZyBkZXIgRmlsbWUsIHdlbGNoZSBiZWkgSUJDRiBmw7xyIHBhYXJ3ZWlzZSDDhGhubGljaGtlaXRzdmVyZ2xlaWNoZSB2ZXJ3ZW5kZXQgd2VyZGVuLg0KRGV0ZXJtaW5lIHRoZSBkaXN0cmlidXRpb24gb2YgZmlsbXMgdXNlZCBpbiBJQkNGIGZvciBwYWlyd2lzZSBzaW1pbGFyaXR5IGNvbXBhcmlzb25zDQoNCmBgYHtyfQ0KIyBIZXJlIG9ubHkgZXhoaWJpdCB0aGUgZmlyc3QgNTAgcm93cyBhbmQgY29sdW1ucw0KZ2V0X21vZGVsX0lCQ0YgPC0gZ2V0TW9kZWwobW9kZWxfSUJDRikgDQppbWFnZShnZXRfbW9kZWxfSUJDRiRzaW1bMTo1MCwgMTo1MF0sIG1haW4gPSAiU2ltaWxhcml0eSBvZiB0aGUgZmlyc3QgNTAgcm93cyBhbmQgY29sdW1ucyIpDQoNCmBgYA0KDQojIyMgVGhlIHNpbWlsYXJpdHkgbWF0cml4IGlzIG5vdCBzeW1tZXRyaWMuIEVhY2ggcm93IGhhcyAzMCBlbGVtZW50cyBsYXJnZXIgdGhhbiAwLiBJbiBlYWNoIGNvbHVtbiwgdGhlIG51bWJlciBvZiBlbGVtZW50cyBncmVhdGVyIHRoYW4gMCBpbmRpY2F0ZXMgaG93IG1hbnkgdGltZXMgdGhpcyBmaWxtIHdhcyBpbmNsdWRlZCBpbiB0aGUgVE9QIGxpc3Qgb2Ygb3RoZXIgZmlsbXMuDQoNCmBgYHtyfQ0KSUJDRl9zaW0gPC0gYXMuZGF0YS5mcmFtZShjb2xTdW1zKGdldF9tb2RlbF9JQkNGJHNpbSA+IDApKSANCmNvbG5hbWVzKElCQ0Zfc2ltKSA8LSAicmVjb21tZW5kZWRfZnJlcXVlbmN5IiAjIGZyZXF1ZW5jeSB0aGF0IHRoZSBjb3JyZXNwb25kaW5nIGZpbG0gaXMgaW5jbHVkZWQgaW4gb3RoZXIgZmlsbXMnIFRPUC1OIGxpc3RzDQoNCmdncGxvdChJQkNGX3NpbSwgYWVzKHg9SUJDRl9zaW0kcmVjb21tZW5kZWRfZnJlcXVlbmN5KSkrZ2VvbV9oaXN0b2dyYW0oZmlsbD0iYmxhY2siLCBjb2w9ImdyZXkiLGJpbndpZHRoID0gNSkrDQogIGxhYnMoeCA9ICJSZWNvbW1lbmRlZCBmcmVxdWVuY3kiLCB5ID0gIkNvdW50IiwgdGl0bGUgPSAiRGlzdHJpYnV0aW9uIG9mIHJlY29tbWVuZGVkIGZyZXF1ZW5jeSBwZXIgZmlsbSIpICsNCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQoNCmBgYA0KIyMjIFRoZSBwbG90IGRpc3BsYXlzIHRoZSBkaXN0cmlidXRpb24gb2YgZmlsbXMgYnkgaG93IG1hbnkgdGltZXMgdGhlIGNvcnJlc3BvbmRpbmcgZmlsbSBpbmNsdWRlZCBpbiB0aGUgVE9QIGxpc3Qgb2Ygb3RoZXIgZmlsbXMuIEZvciBpbnN0YW5jZSwgYWJvdXQgNTIgZmlsbXMgYXJlIG5vdCBpbmNsdWRlZCBpbiBhbnkgVE9QIGxpc3Qgb2Ygb3RoZXIgZmlsbXMsIGFib3V0IDEwMCBmaWxtcyBhcmUgaW5jbHVkZWQgaW4gdGhlIFRPUCBsaXN0cyBvZiA1IGZpbG1zLiBUaGUgaGlnaGVzdCBmcmVxdWVuY3kgaXMgYWJvdXQgMTYwLg0KDQoNCg0KNC40IEJlc3RpbW1lIGRpZSBGaWxtZSwgZGllIGFtIGjDpHVmaWdzdGVuIGluIGRlciBDb3NpbmUtw4RobmxpY2hrZWl0c21hdHJpeCBhdWZ0YXVjaGVuIHVuZCBhbmFseXNpZXJlIGRlcmVuIFZvcmtvbW1lbiB1bmQgUmF0aW5ncyBpbSByZWR1emllcnRlbiBEYXRlbnNhdHouIA0KDQojIyMgZGllIGFtIGjDpHVmaWdzdGVuIEZpbG0gaW4gZGVyIENvc2luZS3DhGhubGljaGtlaXRzbWF0cml4IA0KYGBge3J9DQojIGRpZSAxMCBhbSBow6R1Zmlnc3RlbiBGaWxtZSBpbiBkZXIgQ29zaW5lIMOEaG5saWNoa2VpdHNtYXRyaXgsIGkuZS4gZGllIEZpbG1lIG1pdCBkZXIgaMO2aGVzdGUgc3VtIMOEaG5saWNoa2VpdHMNCmhpZ2hfZnJlcV9maWxtIDwtIElCQ0Zfc2ltICU+JSBtdXRhdGUoZmlsbSA9IHJvd25hbWVzKElCQ0Zfc2ltKSkgJT4lIGFycmFuZ2UoZGVzYyhyZWNvbW1lbmRlZF9mcmVxdWVuY3kpKSAlPiUgc2xpY2UoMDoxMCkgICU+JSBzZWxlY3QoZmlsbSxyZWNvbW1lbmRlZF9mcmVxdWVuY3kpDQpoaWdoX2ZyZXFfZmlsbSANCmBgYA0KIyMjIFRoZSBNb3VzZSBIdW50IGlzIHRoZSBtb3N0IG9mdGVuIHJlY29tbWVuZGVkIGZpbG0uDQoNCg0KDQojIyMgZGllIFZvcmtvbW1lbiB1bmQgUmF0aW5ncyBpbiByZWR1emllcnRlbiBEYXRlbnNhdHoNCmBgYHtyfQ0KdCA8LSBkZl9yZWR1Y2VkX3QgJT4lIG11dGF0ZShpc19OQSA9IHJvd1N1bXMoaXMubmEoZGZfcmVkdWNlZF90KSksbm90X05BID0gcm93U3VtcyghaXMubmEoZGZfcmVkdWNlZF90KSksb2NjdXJyZW5jZSA9IHJvd1N1bXMoIWlzLm5hKGRmX3JlZHVjZWRfdCkpL2RpbShkZl9yZWR1Y2VkX3QpWzJdLCBmaWxtID0gcm93bmFtZXMoZGZfcmVkdWNlZF90KSkgJT4lIHNlbGVjdChpc19OQSxub3RfTkEsb2NjdXJyZW5jZSxmaWxtKQ0KT2NjdXJyZW5jZSA8LSBsZWZ0X2pvaW4oaGlnaF9mcmVxX2ZpbG0sdCxieSA9ICJmaWxtIikgJT4lIHNlbGVjdChmaWxtLHJlY29tbWVuZGVkX2ZyZXF1ZW5jeSxvY2N1cnJlbmNlKSANCnQyIDwtIGRmX3JlZHVjZWRfdCAlPiUgbXV0YXRlKGZpbG0gPSByb3duYW1lcyhkZl9yZWR1Y2VkX3QpLCBhdmdfcmF0aW5nID0gcm93TWVhbnMoZGZfcmVkdWNlZF90LG5hLnJtPVRSVUUpKSU+JSBzZWxlY3QoZmlsbSxhdmdfcmF0aW5nKQ0KT2NjdXJyZW5jZSA8LSBsZWZ0X2pvaW4oT2NjdXJyZW5jZSx0MixieSA9ICJmaWxtIikNCk9jY3VycmVuY2UgICMgb2NjdXJyZW5jZTogbm90X05BIC8gdXNlciBudW1iZXIsIHRoZSB1c2VyIHJhdGlvIHRoYXQgcmF0ZWQgdGhpcyBmaWxtDQpgYGANCiMjIyByZWNvbW1lbmRlZF9mcmVxdWVuY3k6IHRoZSBmcmVxdWFuZWN5IHRoYXQgdGhpcyBpdGVtIGFwcGVhcnMgaW4gdGhlIHRvcC1uIHJlY29tbWVuZGF0aW9uIGxpc3Qgb2Ygb3RoZXIgdXNlcnMuIA0KIyMjIG9jY3VycmVuY2U6IHJhdGlvIHRoYXQgdGhlIGZpbG0gaXMgcmF0ZWQgdG8gYWxsIHVzZXJzDQojIyMgYXZnX3JhdGluZzogdGhlIGF2ZXJhZ2UgcmF0aW5nIG9mIGVhY2ggZmlsbQ0KIyMjIEZyb20gdGhlIHJlc3VsdCwgd2UgY291bGQgc2VlIHRoYXQsIHRoZXJlIGFyZSBubyBkaXJlY3QgcmVsYXRpb25zaGlwIGJldHdlZW4gdGhlIHRocmVlIHZhcmlhYmxlcy4gVGhlIG1vc3Qgb2Z0ZW4gcmVjb21tZW5kZWQgZmlsbSBNb3VzZSBIdW50IGhhcyBhIHJlbGF0aXZlbHkgbG93IGF2ZXJhZ2UgcmF0aW5nIDIuMzIsIGFuZCBtZWRpdW0gb2NjdXJyZW5jZS4NCg0KDQoNCjUgQW5hbHlzZSBUb3AtTiBMaXN0ZW4gSUJDRiB2cyBVQkNGIFZlcmdsZWljaGUgdW5kIGRpc2t1dGllcmUgVG9wIE4gRW1wZmVobHVuZ2VuIHZvbiBJQkNGIHVuZCBVQkNGIE1vZGVsbGVuIG1pdCAzMCBOYWNoYmFybiB1bmQgQ29zaW5lIFNpbWlsYXJpdHkgZsO8ciBkZW4gcmVkdXppZXJ0ZW4gRGF0ZW5zYXR6Lg0KQW5hbHlzaXMgVG9wLU4gbGlzdHMgSUJDRiB2cyBVQkNGLiBDb21wYXJlIGFuZCBkaXNjdXNzIHRvcCBOIHJlY29tbWVuZGF0aW9ucyBmcm9tIElCQ0YgYW5kIFVCQ0YgbW9kZWxzIHdpdGggMzAgbmVpZ2hib3JzIGFuZCBjb3NpbmUgc2ltaWxhcml0eSBmb3IgdGhlIHJlZHVjZWQgZGF0YSBzZXQuDQoNCjUuMSBCZXJlY2huZSBUb3AgMTUgRW1wZmVobHVuZ2VuIGbDvHIgVGVzdGt1bmRlbiBtaXQgSUJDRiB1bmQgVUJDRg0KDQpgYGB7cn0NCiMjIHRvcC1OIHJlY29tbWVuZGF0aW9ucyBmb3IgdGVzdGRhdGEgdXNlcnMgd2l0aCBJQkNGDQpQcmVkX0lCQ0YgPC0gcHJlZGljdChvYmplY3QgPSBtb2RlbF9JQkNGLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd24sIG4gPSAxNSx0eXBlPWMoInRvcE5MaXN0IikpDQoNClRPUDE1X0lCQ0YgPC0gc2FwcGx5KFByZWRfSUJDRkBpdGVtcywgZnVuY3Rpb24oeCkge2NvbG5hbWVzKGRmX3JlZHVjZWQpW3hdfSkNClRPUDE1X0lCQ0ZbLDE6Ml0gICMgaGVyZSBvbmx5IGRpc3BsYXkgdGhlIHRvcCAxNSByZWNvbW1lbmRhdGlvbnMgZm9yIHRoZSBmaXJzdCB0d28gdGVzdCB1c2Vycw0KYGBgDQoNCg0KYGBge3J9DQojIHByZWRpY3Qgd2l0aCBVQkNGDQptb2RlbF9VQkNGIDwtIFJlY29tbWVuZGVyKHJybV9yZWR1Y2VkX3RyYWluLG1ldGhvZD0iVUJDRiIscGFyYW09bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsbWV0aG9kPSJDb3NpbmUiLG5uPTMwKSkgI21vZGVsDQojIHRvcC1OIHJlY29tbWVuZGF0aW9ucyBmb3IgdGVzdGRhdGEgdXNlcnMgd2l0aCBVQkNGDQpQcmVkX1VCQ0YgPC0gcHJlZGljdChvYmplY3QgPSBtb2RlbF9VQkNGLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd24sIG4gPSAxNSx0eXBlPWMoInRvcE5MaXN0IikpIA0KI1RPUDE1X1VCQ0YgPC0gYXMoUHJlZF9VQkNGLCAibGlzdCIpDQpUT1AxNV9VQkNGIDwtIHNhcHBseShQcmVkX1VCQ0ZAaXRlbXMsIGZ1bmN0aW9uKHgpIHtjb2xuYW1lcyhkZl9yZWR1Y2VkKVt4XX0pDQpUT1AxNV9VQkNGWywxOjJdICMgaGVyZSBvbmx5IGRpc3BsYXkgdGhlIHRvcCAxNSByZWNvbW1lbmRhdGlvbnMgZm9yIHRoZSBmaXJzdCB0d28gdGVzdCB1c2Vycw0KYGBgDQoNCjUuMiBWZXJnbGVpY2hlIGRpZSBUb3AgMTUgRW1wZmVobHVuZ2VuIHVuZCBkZXJlbiBWZXJ0ZWlsdW5nIHVuZCBkaXNrdXRpZXJlIEdlbWVpbnNhbWtlaXRlbiB1bmQgVW50ZXJzY2hpZWRlIHp3aXNjaGVuIElCQ0YgdW5kIFVCQ0YgZsO8ciBhbGxlIFRlc3RrdW5kZW4uDQoNCiMjIyBGcm9tIGFib3ZlIHRoZSByZXN1bHQgZm9yIGZpcnN0IHR3byB1c2Vycywgd2UgY291bGQgc2VlIHRoYXQgdGhlIHRvcCAxNSByZWNvbW1lbmRhdGlvbnMgZm9yIHRoZSBzYW1lIHVzZXIgYmV0d2VlbiB0aGUgSUJDRiBhbmQgVUJDRiBtb2RlbHMgYXJlIGNvbXBsZXRlbHkgZGlmZmVyZW50Lg0KDQoNCkNvbXBhcmUgdGhlIHRvcCAxNSByZWNvbW1lbmRhdGlvbnMgZm9yIGFsbCB0ZXN0IHVzZXJzIA0KRmlyc3QgaWRlbnRpZnkgdGhlIG1vc3QgcmVjb21tZW5kZWQgbW92aWVzIGluIHRoZSBUT1AtMTUgbGlzdCBmcm9tIGFsbCB0ZXN0IHVzZXJzLiANCmBgYHtyfQ0KIyBnZW5lcmF0ZSBmcmVxdWVuY3kgdGFibGVzIDogYWxsIHRoZSByZWNvbW1lbmRhdGlvbiBmaWxtcyB3aXRoIHRoZSBjb3JyZXNwb25kaW5nIGZyZXF1ZW5jaWVzIA0KDQpmaWxtX2ZyZXFfSUJDRiA8LSBhcy5kYXRhLmZyYW1lKHRhYmxlKGFzLmZhY3RvcihUT1AxNV9JQkNGKSkpIA0KY29sbmFtZXMoZmlsbV9mcmVxX0lCQ0YpIDwtIGMoIkZpbG1fYnlfSUJDRiIsICJGcmVxdWVuY3kiKSANCg0KZmlsbV9mcmVxX1VCQ0YgPC0gYXMuZGF0YS5mcmFtZSh0YWJsZShhcy5mYWN0b3IoVE9QMTVfVUJDRikpKQ0KY29sbmFtZXMoZmlsbV9mcmVxX1VCQ0YpIDwtIGMoIkZpbG1fYnlfVUJDRiIsICJGcmVxdWVuY3kiKQ0KDQpoZWFkKGZpbG1fZnJlcV9JQkNGICU+JSBhcnJhbmdlKGRlc2MoRnJlcXVlbmN5KSksMTUpDQpoZWFkKGZpbG1fZnJlcV9VQkNGICU+JSBhcnJhbmdlKGRlc2MoRnJlcXVlbmN5KSksMTUpDQpgYGANCg0KYGBge3J9DQpnZ3Bsb3QoaGVhZChmaWxtX2ZyZXFfSUJDRiAlPiUgYXJyYW5nZShkZXNjKEZyZXF1ZW5jeSkpLDE1KSxhZXMoeCA9IHJlb3JkZXIoRmlsbV9ieV9JQkNGLEZyZXF1ZW5jeSksIHkgPSBGcmVxdWVuY3kpKSArIGdlb21fY29sKCkgKyBjb29yZF9mbGlwKCkgKw0KICBsYWJzKHk9IkZyZXF1ZW5jeSIsIHg9IkZpbG0iLHRpdGxlPSJEaXN0cmlidXRpb24gb2YgdGhlIFRvcC0xNSBmaWxtcyBmb3IgYWxsIHRoZSB1c2VycyB3aXRoIElCQ0YiKSArIA0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkNCmBgYA0KDQpgYGB7cn0NCmdncGxvdChoZWFkKGZpbG1fZnJlcV9VQkNGICU+JSBhcnJhbmdlKGRlc2MoRnJlcXVlbmN5KSksMTUpLGFlcyh4ID0gcmVvcmRlcihGaWxtX2J5X1VCQ0YsRnJlcXVlbmN5KSwgeSA9IEZyZXF1ZW5jeSkpICsgZ2VvbV9jb2woKSArIGNvb3JkX2ZsaXAoKSArDQogIGxhYnMoeT0iRnJlcXVlbmN5IiwgeD0iRmlsbSIsdGl0bGU9IkRpc3RyaWJ1dGlvbiBvZiB0aGUgVG9wLTE1IGZpbG1zIGZvciBhbGwgdGhlIHVzZXJzIHdpdGggVUJDRiIpICsgDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQ0KYGBgDQoNCiMjIyBUaGUgbWF4aW11bSByZWNvbW1lbmRlZCBmcmVxdWVuY3kgd2l0aCBJQkNGIGFuZCBVQkNGIGFyZSAyNiBhbmQgMjggcmVzcGVjdGl2ZWx5LCBhbmQgbWluaW11bSBvZiAxNSBhbmQgMTMuIEhvd2V2ZXIgY29tcGFyaW5nIHRvIHRoZSBJQkNGLCB0aGUgZGlzdHJpYnV0aW9uIGluIFVCQ0YgaGFzIGEgbG9uZ2VyIHRhaWwuIFRoaXMgbWVhbnMgd2l0aCB0aGUgVUJDRiBtb2RlbCwgc29tZSBtb3ZpZXMgYXJlIHJlY29tbWVuZGVkIG11Y2ggbW9yZSBvZnRlbiB0aGFuIHRoZSBvdGhlcnMuDQoNCg0KNiBBbmFseXNlIFRvcC1OIExpc3RlbiBSYXRpbmdzDQpVbnRlcnN1Y2hlIGRlbiBFaW5mbHVzcyB2b24gUmF0aW5ncyAob3JkaW5hbGUgdnMgYmluw6RyZSBSYXRpbmdzKSB1bmQgTW9kZWxsdHlwIChJQkNGIHZzIFVCQ0YpIGF1ZiBUb3AgTiBFbXBmZWhsdW5nZW4gZsO8ciBkZW4gcmVkdXppZXJ0ZW4gRGF0ZW5zYXR6Lg0KDQo2LjEgVmVyZ2xlaWNoZSBkZW4gQW50ZWlsIMO8YmVyZWluc3RpbW1lbmRlciBFbXBmZWhsdW5nZW4gZGVyIFRvcCAxNSBMaXN0ZSBmw7xyIElCQ0YgdnMgVUJDRiwgYmVpZGUgbWl0IG9yZGluYWxlbSBSYXRpbmcgdW5kIENvc2luZSBTaW1pbGFyaXR5IGbDvHIgYWxsZSBUZXN0a3VuZGVuDQoNCmBgYHtyfQ0KIyB0aGUgdGVzdCB1c2VyICJ1bmtub3duIiByYXRpbmdzDQpteF9yZWR1Y2VkX3Vua25vd24gPC0gYXMocnJtX3JlZHVjZWRfdW5rbm93biwibWF0cml4IikNCg0KIyBwcmVkaWN0IHRoZSByYXRpbmdzIG9mIHRlc3QgdXNlcnMgYnkgSUJDRiBhbmQgVUJDRg0KcHJlZF9yYXRpbmdfSUJDRiA8LSBhcyhwcmVkaWN0KG9iamVjdCA9IG1vZGVsX0lCQ0YsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93biwgbiA9IDE1LHR5cGU9InJhdGluZ3MiKSwibWF0cml4IikNCnByZWRfcmF0aW5nX1VCQ0YgPC0gYXMocHJlZGljdChvYmplY3QgPSBtb2RlbF9VQkNGLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd24sIG4gPSAxNSx0eXBlPSJyYXRpbmdzIiksIm1hdHJpeCIpDQoNCiMgZXZhbHVhdGUgcmVjb21tZW5kYXRpb25zIG9uICJ1bmtub3duIiByYXRpbmdzDQphY2NfSUIgPC0gY2FsY1ByZWRpY3Rpb25BY2N1cmFjeShwcmVkaWN0KG9iamVjdCA9IG1vZGVsX0lCQ0YsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93biwgbiA9IDE1LHR5cGU9InJhdGluZ3MiKSxycm1fcmVkdWNlZF91bmtub3duKQ0KYWNjX1VCIDwtIGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocHJlZGljdChvYmplY3QgPSBtb2RlbF9VQkNGLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd24sIG4gPSAxNSx0eXBlPSJyYXRpbmdzIikscnJtX3JlZHVjZWRfdW5rbm93bikNCmFjY19vcmRpbmFsIDwtIHJiaW5kKGFjY19JQixhY2NfVUIpDQpyb3duYW1lcyhhY2Nfb3JkaW5hbCkgPC0gYygiSUJDRiBvcmRpbmFsIiwiVUJDRiBvcmRpbmFsIikNCmFjY19vcmRpbmFsDQpgYGANCiMjIyB0aGUgVUJDRiBtb2RlbCB3aXRoIG9yZGluYWwgcmF0aW5ncyBhbmQgY29zaW5lIHNpbWlsYXJpdHkgaGFzIGJldHRlciBhY2N1cmFjeS4NCg0KDQo2LjIgVmVyZ2xlaWNoZSBkZW4gQW50ZWlsIMO8YmVyZWluc3RpbW1lbmRlciBFbXBmZWhsdW5nZW4gZGVyIFRvcCAxNSBMaXN0ZSBmw7xyIElCQ0YgdnMgVUJDRiwgYmVpZGUgbWl0IGJpbsOkcmVtIFJhdGluZyB1bmQgSmFjY2FyZCBTaW1pbGFyaXR5IGbDvHIgYWxsZSBUZXN0a3VuZGVuDQoNCmBgYHtyfQ0KIyBjb252ZXJ0IHRoZSByZWR1Y2VkIGRhdGFzZXQgdG8gYmluYXJ5OiByYXRpbmdzID4gMyBjb252ZXJ0ZWQgYXMgMSwgcmF0aW5ncyA8PSAzIGNvbnZlcnRlZCBhcyAwIA0KZGZfcmVkdWNlZF9iaSA8LSBkZl9yZWR1Y2VkDQpkZl9yZWR1Y2VkX2JpW2RmX3JlZHVjZWRfYmkgPD0gM10gPC0gMA0KZGZfcmVkdWNlZF9iaVtkZl9yZWR1Y2VkX2JpID4gM10gPC0gMQ0KDQpzZXQuc2VlZCg0NjgpDQpteF9yZWR1Y2VkX2JpIDwtIGFzLm1hdHJpeChkZl9yZWR1Y2VkX2JpKQ0KcnJtX3JlZHVjZWRfYmkgPC0gYXMobXhfcmVkdWNlZF9iaSwicmVhbFJhdGluZ01hdHJpeCIpDQp0cmFpbl90ZXN0X2JpIDwtIGV2YWx1YXRpb25TY2hlbWUocnJtX3JlZHVjZWRfYmksIG1ldGhvZD0ic3BsaXQiLCB0cmFpbj0wLjgsIGs9MSwgZ2l2ZW49MjApDQoNCiMgdHJhaW5pbmcgZGF0YSA4MCUgb2YgdGhlIHVzZXJzDQpycm1fcmVkdWNlZF90cmFpbl9iaSA8LSBnZXREYXRhKHRyYWluX3Rlc3RfYmksInRyYWluIikNCg0KIyB0ZXN0IGRhdGEgaXMgMjAlIG9mIHRoZSBhbGwgdXNlcnMsIHRoZSB0ZXN0IGRhdGEgaXMgc3BsaXRlZCBpbnRvIHR3byBwYXJ0czoga25vd24gdGVzdCBkYXRhIGFuZCB1bmtub3duIHRlc3QgZGF0YQ0KIyB0aGUga25vd24gcG9ydGlvbiByZXR1cm5zIHNwZWNpZmllZCAyMCBpdGVtcyBwZXIgdGVzdCB1c2VyIGlzIHVzZWQgdG8gcHJlZGljdCByYXRpbmdzIG9yIGZpbG1zIGZvciB0aGUgdGVzdCB1c2Vycw0KcnJtX3JlZHVjZWRfa25vd25fYmkgPC0gZ2V0RGF0YSh0cmFpbl90ZXN0X2JpLCJrbm93biIpDQoNCiMgdGhlIHVua25vd24gcG9ydGlvbiBpcyB1c2VkIHRvIGNvbXB1dGUgdGhlIHByZWRpY3Rpb24gZXJyb3Igb2YgdGhlIG1vZGVsDQpycm1fcmVkdWNlZF91bmtub3duX2JpIDwtIGdldERhdGEodHJhaW5fdGVzdF9iaSwidW5rbm93biIpDQoNCiMgdHJhaW4gdGhlIElCQ0Ygb3IgVUJDRiBtb2RlbCBvbiB0cmFpbmluZyBkYXRhc2V0DQptb2RlbF9JQkNGX2JpIDwtIFJlY29tbWVuZGVyKGRhdGEgPSBycm1fcmVkdWNlZF90cmFpbl9iaSxtZXRob2Q9IklCQ0YiLHBhcmFtZXRlcj1saXN0KG5vcm1hbGl6ZSA9ICJaLXNjb3JlIixtZXRob2Q9IkphY2NhcmQiLGs9MzApKQ0KbW9kZWxfVUJDRl9iaSA8LSBSZWNvbW1lbmRlcihkYXRhID0gcnJtX3JlZHVjZWRfdHJhaW5fYmksbWV0aG9kPSJVQkNGIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsbWV0aG9kPSJKYWNjYXJkIixubj0zMCkpDQoNCiMgcHJlZGljdCB0aGUgcmF0aW5ncyBvZiB0ZXN0IHVzZXJzIGJ5IElCQ0YgYW5kIFVCQ0YNCnByZWRfcmF0aW5nX0lCQ0ZfYmkgPC0gYXMocHJlZGljdChvYmplY3QgPSBtb2RlbF9JQkNGX2JpLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd25fYmksIG4gPSAxNSx0eXBlPSJyYXRpbmdzIiksIm1hdHJpeCIpDQpwcmVkX3JhdGluZ19VQkNGX2JpIDwtIGFzKHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfVUJDRl9iaSwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duX2JpLCBuID0gMTUsdHlwZT0icmF0aW5ncyIpLCJtYXRyaXgiKQ0KDQojIHRoZSB0ZXN0IHVzZXIgInVua25vd24iIHJhdGluZ3MNCm14X3JlZHVjZWRfdW5rbm93bl9iaSA8LSBhcyhycm1fcmVkdWNlZF91bmtub3duX2JpLCJtYXRyaXgiKQ0KDQojIGV2YWx1YXRlIHJlY29tbWVuZGF0aW9ucyBvbiAidW5rbm93biIgcmF0aW5ncw0KYWNjX0lCX2JpIDwtIGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocHJlZGljdChvYmplY3QgPSBtb2RlbF9JQkNGX2JpLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd25fYmksIG4gPSAxNSx0eXBlPSJyYXRpbmdzIikscnJtX3JlZHVjZWRfdW5rbm93bl9iaSkNCmFjY19VQl9iaSA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfVUJDRl9iaSwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duX2JpLCBuID0gMTUsdHlwZT0icmF0aW5ncyIpLHJybV9yZWR1Y2VkX3Vua25vd25fYmkpDQphY2NfYmkgPC0gcmJpbmQoYWNjX0lCX2JpLGFjY19VQl9iaSkNCnJvd25hbWVzKGFjY19iaSkgPC0gYygiSUJDRiBiaW5hcnkiLCJVQkNGIGJpbmFyeSIpDQphY2NfYmkNCmBgYA0KIyMjIHRoZSBVQkNGIG1vZGVsIHdpdGggYmluYXJ5IHJhdGluZ3MgYW5kIGNvc2luZSBzaW1pbGFyaXR5IGhhcyBiZXR0ZXIgYWNjdXJhY3kuDQoNCg0KNi4zIFZlcmdsZWljaGUgZGVuIEFudGVpbCDDvGJlcmVpbnN0aW1tZW5kZXIgRW1wZmVobHVuZ2VuIGRlciBUb3AgMTUgTGlzdGUgZsO8ciBVQkNGIG1pdCBvcmRpbmFsZW0gKENvc2luZSBTaW1pbGFyaXR5KSB2cyBiaW7DpHJlbSBSYXRpbmcgKEphY2NhcmQgU2ltaWxhcml0eSkgZsO8ciBhbGxlIFRlc3RrdW5kZW4uDQoNCmBgYHtyfQ0KcmJpbmQoYWNjX29yZGluYWwsYWNjX2JpKQ0KYGBgDQojIyMgVGhlIG1vZGVsIHdpdGggYmluYXJ5IHJhdGluZ3MgaGF2ZSBsYXJnZWx5IGltcHJvdmVkIHRoZSBhY2N1cmFjeSBjb21wYXJpbmcgdG8gdGhlIG1vZGVscyB3aXRoIG9yZGluYWwgcmF0aW5ncy4NCg0KDQo3ICBBbmFseXNlIFRvcC1OIExpc3RlbiAtSUJDRiB2cyBTVkQNCkF1ZmdhYmU6IFZlcmdsZWljaGUgTWVtb3J5LWJhc2VkIElCQ0YgdW5kIE1vZGVsbC1iYXNlZCBTVkQgUmVjb21tZW5kZXJzIGJlesO8Z2xpY2ggw5xiZXJzY2huZWlkdW5nIGlocmVyIFRvcC1OIEVtcGZlaGx1bmdlbg0KZsO8ciBkaWUgVXNlci1JdGVtIE1hdHJpeCBkZXMgcmVkdXppZXJ0ZW4gRGF0ZW5zYXR6ZXMgKEJhc2lzOiBJQkNGIG1pdCAzMCBOYWNoYmFybiB1bmQgQ29zaW5lIFNpbWlsYXJpdHkpLg0KDQoxLiBWZXJnbGVpY2hlIHdpZSBzaWNoIGRlciBBbnRlaWwgw7xiZXJlaW5zdGltbWVuZGVyIEVtcGZlaGx1bmdlbiBkZXIgVG9wLTE1IExpc3RlIGbDvHIgSUJDRiB2cyB2ZXJzY2hpZWRlbmUgU1ZEIE1vZGVsbGUgdmVyw6RuZGVydCwgd2VubiBkaWUgQW56YWhsIGRlciBTaW5ndWzDpHJ3ZXJ0ZSBmw7xyIFNWRCB2b24gMTAgYXVmIDIwLCAzMCwgNDAsIDUwIHZlcsOkbmRlcnQgd2lyZC4NCg0KYGBge3J9DQoNCiMgU1ZEIE1PREVMDQptb2RlbF9TVkRfMTAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz0xMCkpDQptb2RlbF9TVkRfMjAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz0yMCkpDQptb2RlbF9TVkRfMzAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz0zMCkpDQptb2RlbF9TVkRfNDAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz00MCkpDQptb2RlbF9TVkRfNTAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz01MCkpDQoNCiMgZXZhbHVhdGUgcmVjb21tZW5kYXRpb25zIG9uICJ1bmtub3duIiByYXRpbmdzDQphY2NfU1ZEXzEwIDwtIGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocHJlZGljdChvYmplY3QgPSBtb2RlbF9TVkRfMTAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93biwgbiA9IDE1LHR5cGU9InRvcE5MaXN0IikscnJtX3JlZHVjZWRfdW5rbm93bixnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCmFjY19TVkRfMjAgPC0gY2FsY1ByZWRpY3Rpb25BY2N1cmFjeShwcmVkaWN0KG9iamVjdCA9IG1vZGVsX1NWRF8yMCwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duLCBuID0gMTUsdHlwZT0idG9wTkxpc3QiKSxycm1fcmVkdWNlZF91bmtub3duLGdpdmVuPTIwLGdvb2RSYXRpbmcgPSA0KQ0KYWNjX1NWRF8zMCA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfU1ZEXzMwLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd24sIG4gPSAxNSx0eXBlPSJ0b3BOTGlzdCIpLHJybV9yZWR1Y2VkX3Vua25vd24sZ2l2ZW49MjAsZ29vZFJhdGluZyA9IDQpDQphY2NfU1ZEXzQwIDwtIGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocHJlZGljdChvYmplY3QgPSBtb2RlbF9TVkRfNDAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93biwgbiA9IDE1LHR5cGU9InRvcE5MaXN0IikscnJtX3JlZHVjZWRfdW5rbm93bixnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCmFjY19TVkRfNTAgPC0gY2FsY1ByZWRpY3Rpb25BY2N1cmFjeShwcmVkaWN0KG9iamVjdCA9IG1vZGVsX1NWRF81MCwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duLCBuID0gMTUsdHlwZT0idG9wTkxpc3QiKSxycm1fcmVkdWNlZF91bmtub3duLGdpdmVuPTIwLGdvb2RSYXRpbmcgPSA0KQ0KDQphY2NfSUJDRl90b3AxNSA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfSUJDRiwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duLCBuID0gMTUsdHlwZT0idG9wTkxpc3QiKSxycm1fcmVkdWNlZF91bmtub3duLGdpdmVuPTIwLGdvb2RSYXRpbmcgPSA0KQ0KDQphY2NfU1ZEX0lCIDwtIHJiaW5kKGFjY19TVkRfMTAsYWNjX1NWRF8yMCxhY2NfU1ZEXzMwLGFjY19TVkRfNDAsYWNjX1NWRF81MCxhY2NfSUJDRl90b3AxNSkNCnJvd25hbWVzKGFjY19TVkRfSUIpIDwtIGMoIlNWRF9rXzEwIiwiU1ZEX2tfMjAiLCJTVkRfa18zMCIsIlNWRF9rXzQwIiwiU1ZEX2tfNTAiLCJJQkNGX2Nvc19rXzMwIikNCmFjY19TVkRfSUINCmBgYA0KIyMjIFRoZSBtb2RlbCB3aXRoIFNWRCBhbmQgMTAgbmVpZ2hib3JzIGhhdmUgdGhlIGJlc3QgcHJlY2lzaW9uIGFuZCByZWNhbGwuIA0KIyMjIFNWRCBrPTEwID4gU1ZEIGs9MjAgPiBTVkQgaz00MCA+IFNWRCBrPTMwID4gSUJDRiBjb3NpbmUgaz0zMCA+IFNWRCBrPTUwDQoNCg0KOCBXYWhsIGRlcyBvcHRpbWFsZW4gUmVjb21tZW5kZXJzIEF1ZmdhYmU6IA0KQmVzdGltbWUgYXVzIDUgdW50ZXJzY2hpZWRsaWNoZW4gTW9kZWxsZW4gZGFzIGhpbnNpY2h0bGljaCBUb3AtTiBFbXBmZWhsdW5nZW4gYmVzdGUgTW9kZWxsLiANCkJlZ3LDvG5kZSBkZWluZSBNb2RlbGx3YWhsZW4gYXVmZ3J1bmQgZGVyIGJpc2hlciBnZW1hY2h0ZW4gRXJrZW5udG5pc3NlIHVuZCB2ZXJ3ZW5kZSBhbHMgNi4gTW9kZWxsIGVpbmVuIFRvcC1Nb3ZpZSBSZWNvbW1lbmRlciAoQmFzaXM6IHJlZHV6aWVydGVyIERhdGVuc2F0eikuDQoNCg0KOC4xIFZlcndlbmRlIGbDvHIgZGllIEV2YWx1aWVydW5nIDEwLWZhY2hlIEtyZXV6dmFsaWRpZXJ1bmcNCg0KYGBge3J9DQojY3JlYXRlIDEwLWZvbGQgY3Jvc3MgdmFsaWRhdGlvbiBzY2hlbWUNCnNldC5zZWVkKDY5NTQpDQpzY2hlbWUgPC0gZXZhbHVhdGlvblNjaGVtZShycm1fcmVkdWNlZCwgbWV0aG9kPSJjcm9zcyIsIGs9MTAsIGdpdmVuPTIwLCBnb29kUmF0aW5nPTQpDQoNCiMgZXZhbHVhdGUgd2l0aCBkaWZmZXJlbnQgbWV0aG9kcw0KY3ZfSUJDRiA8LSBldmFsdWF0ZShzY2hlbWUsIG1ldGhvZD0iSUJDRiIsIHR5cGUgPSAidG9wTkxpc3QiLHBhcmFtZXRlcj1saXN0KG5vcm1hbGl6ZSA9ICJaLXNjb3JlIixtZXRob2Q9ImNvc2luZSIsaz0zMCksbj0xNSkNCmN2X1VCQ0YgPC0gZXZhbHVhdGUoc2NoZW1lLCBtZXRob2Q9IlVCQ0YiLCB0eXBlID0gInRvcE5MaXN0IixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsbWV0aG9kPSJjb3NpbmUiLG5uPTMwKSxuPTE1KQ0KY3ZfU1ZEIDwtIGV2YWx1YXRlKHNjaGVtZSwgbWV0aG9kPSJTVkQiLCB0eXBlID0gInRvcE5MaXN0IixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz0zMCksbj0xNSkNCmN2X1JBTkRPTSA8LSBldmFsdWF0ZShzY2hlbWUsbWV0aG9kPSJSQU5ET00iLHR5cGU9InRvcE5MaXN0IixuPTE1KQ0KY3ZfUE9QIDwtIGV2YWx1YXRlKHNjaGVtZSwgbWV0aG9kPSJQT1BVTEFSIiwgdHlwZSA9ICJ0b3BOTGlzdCIscGFyYW1ldGVyPWxpc3Qobm9ybWFsaXplID0gIlotc2NvcmUiKSxuPTE1KQ0KDQojIGdldCB0aGUgYXZlcmFnZWQgZXZhbHVhdGlvbiByZXN1bHRzDQpSZXN1bHRfODEgPC0gcmJpbmQoYXZnKGN2X0lCQ0YpLGF2Zyhjdl9VQkNGKSxhdmcoY3ZfU1ZEKSxhdmcoY3ZfUkFORE9NKSxhdmcoY3ZfUE9QKSkNCnJvd25hbWVzKFJlc3VsdF84MSkgPC0gYygiSUJDRiIsIlVCQ0YiLCJTVkQiLCJSQU5ET00iLCJQT1BVTEFSIikNClJlc3VsdF84MQ0KDQpgYGANCiMjIyBUaGUgbW9kZWwgd2l0aCBwb3B1bGFyIG1ldGhvZCBoYXMgdGhlIGJlc3QgcHJlY2lzaW9uIGFuZCByZWNhbGwuDQojIyMgUG9wdWxhciA+IElCQ0YgfiBTVkQgPiBSQU5ET00gPiBVQkNGDQoNCg0KOC4yIEJlZ3LDvG5kZSBkZWluZSBXYWhsIGRlciBQZXJmb3JtYW5jZSBNZXRyaWssDQoNCiMjIyBIaWdoZXIgcHJlY2lzaW9uIG1lYW5zIHRoYXQgYW4gYWxnb3JpdGhtIHJldHVybnMgbW9yZSByZWxldmFudCByZXN1bHRzIHRoYW4gaXJyZWxldmFudCBvbmVzLCBhbmQgaGlnaCByZWNhbGwgbWVhbnMgdGhhdCBhbiBhbGdvcml0aG0gcmV0dXJucyBtb3N0IG9mIHRoZSByZWxldmFudCByZXN1bHRzICh3aGV0aGVyIG9yIG5vdCBpcnJlbGV2YW50IG9uZXMgYXJlIGFsc28gcmV0dXJuZWQpLg0KDQojIyMgQSBwZXJmZWN0IHByZWNpc2lvbiBzY29yZSBvZiAxLjAgbWVhbnMgdGhhdCBldmVyeSByZXN1bHQgcmV0cmlldmVkIHdhcyByZWxldmFudCAoYnV0IHNheXMgbm90aGluZyBhYm91dCB3aGV0aGVyIGFsbCByZWxldmFudCBkb2N1bWVudHMgd2VyZSByZXRyaWV2ZWQpIHdoZXJlYXMgYSBwZXJmZWN0IHJlY2FsbCBzY29yZSBvZiAxLjAgbWVhbnMgdGhhdCBhbGwgcmVsZXZhbnQgZG9jdW1lbnRzIHdlcmUgcmV0cmlldmVkIGJ5IHRoZSBzZWFyY2ggKGJ1dCBzYXlzIG5vdGhpbmcgYWJvdXQgaG93IG1hbnkgaXJyZWxldmFudCBkb2N1bWVudHMgd2VyZSBhbHNvIHJldHJpZXZlZCkNCg0KIyMjIFRoZSBtb2RlbCBQb3B1bGFyIHJldHVybnMgdGhlIGhpZ2hlc3Qgc2NvcmUgb2YgYm90aCBwcmVjaXNpb24gYW5kIHJlY2FsbC4gDQojIyMgUG9wdWxhciA+IFNWRCB+IElCQ0YgPiBSQU5ET00gPiBVQkNGDQoNCg0KOC4zIEFuYWx5c2llcmUgZGFzIGJlc3RlIE1vZGVsbCBmw7xyIFRvcC1OIFJlY29tbWVuZGF0aW9ucyBtaXQgTiBnbGVpY2ggMTAsIDE1LCAyMCwgMjUgdW5kIDMwLA0KDQpgYGB7cn0NClBPUF9yZXN1bHRzIDwtIGV2YWx1YXRlKHNjaGVtZSwgbWV0aG9kPSJQT1BVTEFSIiwgdHlwZSA9ICJ0b3BOTGlzdCIscGFyYW1ldGVyPWxpc3Qobm9ybWFsaXplID0gIlotc2NvcmUiKSxuPWMoMTAsMTUsMjAsMjUsMzApKQ0KYXZnX1BPUF9yZXN1bHRzIDwtIGF2ZyhQT1BfcmVzdWx0cykNCmF2Z19QT1BfcmVzdWx0cw0KYGBgDQojIyMgV2hlbiBJIGluY3JlYXNlIHRoZSBOLCB0aGUgInJlY2FsbCIgaXMgZ2V0dGluZyBiZXR0ZXIgKGxhcmdlciB2YWx1ZSksIGJ1dCB0aGUgInByZWNpc2lvbiIgaXMgZ2V0dGluZyB3b3JzZSAoc21hbGxlciB2YWx1ZSkuDQoNCg0KOC40IE9wdGltaWVyZSBkZWluIGJlc3RlcyBNb2RlbGwgaGluc2ljaHRsaWNoIEh5cGVycGFyYW1ldGVyLg0KSGlud2VpczogVmVyd2VuZGUgZsO8ciBkZW4gVG9wLU1vdmllIFJlY29tbWVuZGVyIGRpZSBGaWxtZSBtaXQgZGVuIGjDtmNoc3RlbiBEdXJjaHNjaG5pdHRzcmF0aW5ncy4NCg0KYGBge3J9DQojIGZpbG1zIHdpdGggb25seSB0aGUgaGlnaGVzdCBhdmVyYWdlIHJhdGluZ3MgKHJhdGluZ3MgPiAzKQ0KZGZfdG9wX2F2ZyA8LSBhcy5kYXRhLmZyYW1lKHQoZGZfcmVkdWNlZCkpDQpkZl90b3BfYXZnIDwtIGRmX3RvcF9hdmcgJT4lIG11dGF0ZShhdmdfcmF0aW5nID0gcm93TWVhbnMoZGZfdG9wX2F2ZyxuYS5ybT1UUlVFLGRpbXM9MSkpJT4lIGFycmFuZ2UoZGVzYyhhdmdfcmF0aW5nKSklPiUgZmlsdGVyKGF2Z19yYXRpbmc+MykgJT4lIHNlbGVjdCgtYXZnX3JhdGluZykNCnJybV90b3BfYXZnIDwtIGFzKHQoZGZfdG9wX2F2ZyksInJlYWxSYXRpbmdNYXRyaXgiKQ0KDQoNCnNldC5zZWVkKDg0Njk1NCkNCnNjaGVtZV90b3BfYXZnIDwtIGV2YWx1YXRpb25TY2hlbWUocnJtX3RvcF9hdmcsIG1ldGhvZD0iY3Jvc3MiLCBrPTEwLCBnaXZlbj0yMCwgZ29vZFJhdGluZz00KQ0KDQojIHRoZSBtb2RlbCBQb3B1bGFyIGhhcyBvbmx5IG9uZSBwYXJhbWV0ZXI6IG5vcm1hbGl6ZS4gSGVyZSBJIHdpbGwgY29tcGFyZSB0d28gbm9ybWFsaXphdGlvbiBtZXRob2RzOiB6LXNjb3JlIGFuZCBjZW50ZXINClBPUF90b3BfYXZnX3ogPC0gYXZnKGV2YWx1YXRlKHNjaGVtZV90b3BfYXZnLCBtZXRob2Q9IlBPUFVMQVIiLCB0eXBlID0gInRvcE5MaXN0IixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIpLG49YygxMCwxNSwyMCwyNSwzMCkpKQ0KDQpQT1BfdG9wX2F2Z19jZW50ZXIgPC0gYXZnKGV2YWx1YXRlKHNjaGVtZV90b3BfYXZnLCBtZXRob2Q9IlBPUFVMQVIiLCB0eXBlID0gInRvcE5MaXN0IixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiY2VudGVyIiksbj1jKDEwLDE1LDIwLDI1LDMwKSkpDQoNCmRpZmZfel9jZW50ZXIgPC0gY2JpbmQoKFBPUF90b3BfYXZnX3ogLSBQT1BfdG9wX2F2Z19jZW50ZXIpWyw2OjddLFBPUF90b3BfYXZnX3pbLDEwXSkgDQpQT1BfdG9wX2F2Z196OyBQT1BfdG9wX2F2Z19jZW50ZXI7IGRpZmZfel9jZW50ZXINCmBgYA0KIyMjIEhlcmUgSSB0cmllZCB0byBvcHRpbWl6ZSB0aGUgcG9wdWxhciBtb2RlbCB0aHJvdWdoIHRoZSBub3JtYWxpemF0aW9uIHBhcmFtZXRlci4gVGhlIHR3byBub3JtYWxpYXphdGlvbiBtZXRob2RzIHotc2NvcmUgYW5kIGNlbnRlciBoYXZlIHZlcnkgc2ltaWxpYXIgcGVyZm9ybWFuY2Ugb24gdGhlIHByZWNpc2lvbiBhbmQgcmVjYWxsLiBUaGUgbW9kZWxzIHdpdGggei1zY29yZSBoYXMgc2xpZ2h0bHkgYmV0dGVyIHBlcmZvcm1hbmNlIHRoYW4gdGhlIGNlbnRlciBub3JtYWxpemF0aW9uIHdpdGggbiA9IDEwLCAxNSwgMjUsIDMwLiBUaGUgbW9kZWwgd2l0aCBjZW50ZXIgbm9ybWFsaXphdGlvbiBwZXJmb3JtZWQgYSBiaXQgYmV0dGVyIHdpdGggbiA9IDIwLiANCg0KDQo5IEltcGxlbWVudGllcnVuZyDDhGhubGljaGtlaXRzbWF0cml4DQoNCkF1ZmdhYmUgRElZOiBJbXBsZW1lbnRpZXJlIGVpbmUgRnVua3Rpb24genVyIGVmZml6aWVudGVuIEJlcmVjaG51bmcgdm9uIHNwYXJzZW4gw4RobmxpY2hrZWl0c21hdHJpemVuIGbDvHIgSUJDRiBSUyB1bmQgYW5hbHlzaWVyZSBkaWUgUmVzdWx0YXRlIGbDvHIgMTAwIHp1ZsOkbGxpZyBnZXfDpGhsdGUgRmlsbWUuDQoNCjkuMSBJbXBsZW1lbnRpZXJlIGVpbmUgRnVua3Rpb24sIHVtIGbDvHIgb3JkaW5hbGUgUmF0aW5ncyBlZmZpemllbnQgZGllIENvc2luZSBTaW1pbGFyaXR5IHp1IGJlcmVjaG5lbiwNCg0KYGBge3J9DQpjb3Nfc2ltaWxhcml0eSA8LSBmdW5jdGlvbihteCl7DQogICAgbiA8LSBkaW0obXgpWzJdDQogICAgbXhfMCA8LSBteA0KICAgIG14XzBbaXMubmEobXhfMCldIDwtIDANCiAgICBzaW1fbXggPC0gbWF0cml4KDE6bl4yLCBucm93ID0gbikNCiAgICBmb3IoaSBpbiAxOm4pew0KICAgICAgZm9yKGogaW4gMTpuKXsNCiAgICAgICAgIA0KICAgICAgICBudW1lcmF0b3IgPC0gdChteF8wWyxpXSkgJSolIG14XzBbLGpdDQogICAgICAgIGRlbm9taW5hdG9yIDwtIHNxcnQoc3VtKG14XzBbLGldXjIpKSpzcXJ0KHN1bShteF8wWyxqXV4yKSkNCiAgICAgICAgc2ltX214W2ksal0gPC0gbnVtZXJhdG9yL2Rlbm9taW5hdG9yDQogICAgICB9DQogICAgfQ0KICAgIHJldHVybihzaW1fbXgpDQp9DQoNCmNvc19zaW1fcmVkdWNlZF8xIDwtIGNvc19zaW1pbGFyaXR5KGRmX3JlZHVjZWQpDQoNCmBgYA0KDQoNCjkuMiBJbXBsZW1lbnRpZXJlIGVpbmUgRnVua3Rpb24sIHVtIGbDvHIgYmluw6RyZSBSYXRpbmdzIGVmZml6aWVudCBkaWUgSmFjY2FyZCBTaW1pbGFyaXR5IHp1IGJlcmVjaG5lbiwNCg0KDQpgYGB7cn0NCkphY2Nfc2ltaWxhcml0eSA8LSBmdW5jdGlvbihteCl7DQogICAgbXhfYmkgPC0gbXgNCiAgICBteF9iaVtteF9iaSA8PSAzXSA8LSAwIA0KICAgIG14X2JpW2lzLm5hKG14X2JpKV0gPC0gMCAjIHRoZSBOQSBhbmQgcmF0aW5ncyA8PSAzIGFsbCBjb252ZXJ0ZWQgYXMgMA0KICAgIG14X2JpW214X2JpID4gM10gPC0gMSAjIHRoZSByYXRpbmdzID4gMyAod2hpY2ggc2hvd3MgYSBwcmVmZXJlbmNlKSBjb252ZXJ0ZWQgYXMgMQ0KICAgIA0KICAgIG4gPC0gZGltKG14X2JpKVsyXQ0KICAgIA0KICAgIHNpbV9teCA8LSBtYXRyaXgoMTpuXjIsIG5yb3cgPSBuKSAjIGNyZWF0ZSBhIG1hdHJpeCB3aXRoIGRpbWVudGlvbiBvZiBuIHggbiBmb3Igc2ltaWxhcml0eSANCiAgICBmb3IoaSBpbiAxOm4pew0KICAgICAgZm9yKGogaW4gMTpuKXsNCiAgICAgICAgZGlmZiA8LSBzdW0oYWJzKG14X2JpWyxpXSAtIG14X2JpWyxqXSkpICMgdGhlIHN1bSBvZiBhYnNvbHV0ZSBkaWZmZXJlbmNlIGJldHdlZW4gdHdvIHZlY3RvcnM6IHNpbmNlIHRoZSBwYWlycyBhcmUgZWl0aGVyIHNhbWUgb3Igd2l0aCB0aGUgZGlmZmVyZW5jZSBvZiAxLCB0aGlzIG1lYW5zIHRoZSByZXN1bHQgc2hvd3MgYWxzbyBob3cgbWFueSBwYWlycyBhcmUgZGlmZmVyZW50Lg0KICAgICAgICBzaW1fbXhbaSxqXSA8LSAxIC0gZGlmZi9uIA0KICAgICAgfQ0KICAgIH0NCiAgICByZXR1cm4oc2ltX214KQ0KICB9DQoNCkphY2Nfc2ltX3JlZHVjZWQgPC0gSmFjY19zaW1pbGFyaXR5KGRmX3JlZHVjZWQpICAjIGEgNzAwIHggNzAwIHNpbWlsYXJpdHkgbWF0cml4DQpgYGANCg0KDQoNCjkuMyBWZXJnbGVpY2hlIGRlaW5lIEltcGxlbWVudGllcnVuZyBkZXIgQ29zaW5lLWJhc2llcnRlbiDDhGhubGljaGtlaXRzbWF0cml4IGbDvHIgb3JkaW5hbGUgS3VuZGVucmF0aW5ncyBtaXQgZGVyIGtvcnJlc3BvbmRpZXJlbmRlbiB2aWEgT3BlbiBTb3VyY2UgUGFrZXRlbiBlcnpldWd0ZW4gw4RobmxpY2hrZWl0c21hdHJpeCwNCg0KYGBge3J9DQpteF9yZWR1Y2VkXzAgPC0gbXhfcmVkdWNlZA0KbXhfcmVkdWNlZF8wW2lzLm5hKG14X3JlZHVjZWRfMCldPC0wICAjIHJlcGxhY2UgTkEgYXMgMA0KY29zX3NpbV9yZWR1Y2VkXzIgPC0gYXMubWF0cml4KHNpbWlsYXJpdHkoYXMobXhfcmVkdWNlZF8wLCJyZWFsUmF0aW5nTWF0cml4IiksIG1ldGhvZCA9ICJjb3NpbmUiLCB3aGljaCA9ICJpdGVtcyIpKSAjIGNhbGN1bGF0ZSB0aGUgY29zaW5lIHNpbWlsYXJpdHkgbWF0cml4IGJ5IG9wZW4gc291cmNlIHBhY2thZ2UNCg0KIyBTaW5jZSB0aGUgY29zIHNpbWlsYXJpdHkgbWF0cml4IGJ5IHRoaXMgbWV0aG9kIHVzZSAwIGZvciBhbGwgdGhlIGRpYWdvbmFsIGVsZW1lbnRzLCB3aGVyZSBhbGwgYXJlIDEgYnkgdGhlIHVwcGVyIGZ1bmN0aW9uIHRvIHJlbW92ZSB0aGlzIGVmZmVjdCwgaGVyZSBpIHdpbGwgcmVmaWxsIHRoZSBkaWFnb25hbCB3aXRoIDENCmRpYWcoY29zX3NpbV9yZWR1Y2VkXzIpPC0xDQoNCmNvbXBhcmVfdHdvX2Nvc19zaW1fbWV0aG9kcyA8LSBhbGwuZXF1YWwoY29zX3NpbV9yZWR1Y2VkXzEsIGNvc19zaW1fcmVkdWNlZF8yLCB0b2xlcmFuY2UgPSAxZS0xMCxjaGVjay5hdHRyaWJ1dGVzID0gRkFMU0UpDQpjb21wYXJlX3R3b19jb3Nfc2ltX21ldGhvZHMNCmBgYA0KIyMjIFRoZSBjb3NpbmUgc2ltaWxhcml0eSBtYXRyaWNlcyBieSB0d28gZGlmZmVyZW50IG1ldGhvZHMgYXJlIGVxdWFsICh3aXRoIHRvbGVyYW5jZSBvZiAxZS0xMCkuDQoNCg0KDQo5LjQgVmVyZ2xlaWNoZSB1bmQgZGlza3V0aWVyZSBkaWUgVW50ZXJzY2hpZWRlIGRlaW5lciBtaXR0ZWxzIENvc2luZSBTaW1pbGFyaXR5IGVyemV1Z3RlbiDDhGhubGljaGtlaXRzbWF0cml6ZW4gZsO8ciBvcmRpbmFsZSB1bmQgbm9ybWllcnRlIEt1bmRlbnJhdGluZ3MgbWl0IGRlciBKYWNjYXJkLWJhc2llcnRlbiDDhGhubGljaGtlaXRzbWF0cml4Lg0KDQpgYGB7cn0NCmNvbXBhcmVfY29zX0phY2MgPC0gYWxsLmVxdWFsKGNvc19zaW1fcmVkdWNlZF8xLEphY2Nfc2ltX3JlZHVjZWQsdG9sZXJhbmNlID0gMWUtMyxjaGVjay5hdHRyaWJ1dGVzID0gRkFMU0UpDQpjb21wYXJlX2Nvc19KYWNjDQpgYGANCiMjIyBUaGUgbWVhbiByZWxhdGl2ZSBkaWZmZXJlbmNlIGJldHdlZW4gY29zaW5lIHNpbWlsYXJpdHkgYW5kIGphY2NhcmQgc2ltaWxhcml0eSBpcyAyLjQ4Lg0KIyMjIEphY2NhcmQgc2ltaWxhcml0eSB0YWtlcyBvbmx5IHRoZSB1bmlxdWUgc2V0IG9mIGl0ZW1zLiBUaGUgY29zaW5lIHNpbWlsYXJpdHkgdGFrZXMgdGhlIHRvdGFsIGxlbmd0aCBvZiB0aGUgdmVjdG9ycy4NCg0KDQoNCjEwIEltcGxlbWVudGllcnVuZyBUb3AtTiBNZXRyaWtlbg0KDQpBdWZnYWJlIERJWTogSW1wbGVtZW50aWVyZSBGdW5rdGlvbmVuIGbDvHIgZGllIEJldXJ0ZWlsdW5nIGRlciBUb3AtTiBNZXRyaWtlbiBQcmVjaXNpb24gdW5kIFJlY2FsbCBzb3dpZSBmw7xyIGFsbGUgS3VuZGVuIGRlciBJdGVtLXNwYWNlIENvdmVyYWdlIHVuZCBOb3ZlbHR5IHVuZCB0ZXN0ZSBkaWVzZSBtaXQgSUJDRiBSZWNvbW1lbmRhdGlvbnMgKEJhc2lzOiByZWR1emllcnRlciBEYXRlbnNhdHo7IE4gPSA1LCAxMCwgMTUsIDIwLCAyNSwgMzApDQoNCg0KMTAuMSBJbXBsZW1lbnRpZXJlIGVpbmUgRnVua3Rpb24sIHVtIGF1cyBUb3AtTiBMaXN0ZW4gZsO8ciBhbGxlIEt1bmRlbiBkaWUgSXRlbS1zcGFjZSBDb3ZlcmFnZUBOIHVuZCBOb3ZlbHR5QE4gZWluZXMgUmVjb21tZW5kZXJzIHp1IGJldXJ0ZWlsZW4gdW5kIHRlc3RlIGRpZXNlLg0KDQoNCmBgYHtyfQ0KY2FsY190b3BuX21ldHJpY3MgPC0gZnVuY3Rpb24obXgsc3BsaXRfcmF0aW8sTil7ICAjIG14OiBVX0kgZGF0YTsgc3BsaXRfcmF0aW86dHJhaW4gZGF0YSBwcm9wb3J0aW9uOyBuOiBUb3AtTg0KICBycm0gPC0gYXMobXgsInJlYWxSYXRpbmdNYXRyaXgiKQ0KICAjIHNwbGl0IHRyYWluLCB0ZXN0LWtub3duLCB0ZXN0X3Vua25vd24gZGF0YQ0KICB0cmFpbl90ZXN0IDwtIGV2YWx1YXRpb25TY2hlbWUocnJtLCBtZXRob2Q9InNwbGl0IiwgdHJhaW49c3BsaXRfcmF0aW8sIGs9MSwgZ2l2ZW49MjAsZ29vZFJhdGluZz00KQ0KICBycm1fdHJhaW4gPC0gZ2V0RGF0YSh0cmFpbl90ZXN0LCJ0cmFpbiIpDQogIHJybV9rbm93biA8LSBnZXREYXRhKHRyYWluX3Rlc3QsImtub3duIikgDQogIHJybV91bmtub3duIDwtIGdldERhdGEodHJhaW5fdGVzdCwidW5rbm93biIpDQogICMgSUJDRiBtb2RlbA0KICBtb2RlbF9JQkNGIDwtUmVjb21tZW5kZXIoZGF0YSA9IHJybV90cmFpbixtZXRob2Q9IklCQ0YiLHBhcmFtZXRlcj1saXN0KG5vcm1hbGl6ZSA9ICJaLXNjb3JlIixtZXRob2Q9IkNvc2luZSIsaz0xMCkpDQogICMgcHJlZGljdCBUb3AtTiByZWNvbW1lbmRhdGlvbiBsaXN0DQogIHByZWRfSUJDRiA8LSBwcmVkaWN0KG9iamVjdCA9IG1vZGVsX0lCQ0YsIG5ld2RhdGEgPSBycm1fa25vd24sIG4gPSBOLHR5cGU9InRvcE5MaXN0IikNCiAgDQogICMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KICANCiAgIyMjIGFjY3VyYWN5OiBldmFsdWF0ZSB0aGUgcmVjb21tZW5kYXRpb25zIG9uICJ1bmtub3duIiByYXRpbmdzIHdpdGggbWV0cmljcyBwcmVjaXNpb24gYW5kIHJlY2FsbA0KICBhY2NfSUJDRiA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfSUJDRiwgbmV3ZGF0YSA9IHJybV9rbm93biwgbiA9IE4sdHlwZT0idG9wTkxpc3QiKSxycm1fdW5rbm93bixnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCiAgDQogIGFjY19JQkNGIDwtIHQoYXMuZGF0YS5mcmFtZShhY2NfSUJDRikpDQogIHJvd25hbWVzKGFjY19JQkNGKSA8LSBOVUxMDQogIA0KICAjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMNCiAgDQogICMjIyBpdGVtLXNwYWNlIGNvdmVyYWdlOiBob3cgbWFueSBwZXJjZW50YWdlIG9mIGZpbG1zKGZyb20gdGhlIHRyYWluIGRhdGEpIGFyZSBpbiB0aGUgdG9wLW4gcmVjb21tZW5kYXRpb24gbGlzdHMNCiAgIyB0b3AgbiBsaXN0cyBmb3IgZXZlcnkgdXNlcg0KICAgDQogIFRPUF9OX2xpc3QgPC0gc2FwcGx5KHByZWRfSUJDRkBpdGVtcywgZnVuY3Rpb24oeCkge2NvbG5hbWVzKGFzKHJybV9rbm93biwibWF0cml4IikpW3hdfSkgDQogICMgdW5pcXVlIHByZWRpY3RlZCBmaWxtIGxpc3Qgb2YgYWxsIHRlc3QgdXNlcnMgDQogIHVuaXFfZmlsbV90ZXN0IDwtIHJlc2hhcGUyOjptZWx0KGFzKFRPUF9OX2xpc3QsIm1hdHJpeCIpKSAlPiUgcmVuYW1lKFVzZXJJRCA9IFZhcjIsIHJhbmsgPSBWYXIxLCBGaWxtX25hbWUgPSB2YWx1ZSklPiVkaXN0aW5jdChGaWxtX25hbWUpICAgIyB1bmlxdWUgZmlsbSBsaXN0IHJlY29tbWVuZGVkIGluIHRlc3QgZGF0YQ0KICANCiAgIyB1bmlxdWUgZmlsbSBsaXN0IG9mIHRoZSB0cmFpbiBkYXRhDQogIHVuaXFfZmlsbV90cmFpbiA8LSBhcy5kYXRhLmZyYW1lKHQobXgpKQ0KICB1bmlxX2ZpbG1fdHJhaW4kY250IDwtIHJvd1N1bXMoIWlzLm5hKHVuaXFfZmlsbV90cmFpbikpICMgY291bnQgbm90IE5BIGZvciBlYWNoIGZpbG0NCiAgdW5pcV9maWxtX3RyYWluIDwtIHVuaXFfZmlsbV90cmFpbiAlPiUgZmlsdGVyKGNudD4wKSAgIyByZW1vdmUgdGhlIGZpbG0gd2l0aG91dCBhbnkgcmF0aW5ncw0KICANCiAgIyBjYWxjdWxhdGUgdGhlIGl0ZW0tc3BhY2UgY292ZXJhZ2UNCiAgY292ZXJhZ2UgPC0gZGltKHVuaXFfZmlsbV90ZXN0KVsxXSAvIGRpbSh1bmlxX2ZpbG1fdHJhaW4pWzFdICMgdGhlIGNvdmVyYWdlDQogIGNvdmVyYWdlIDwtIGFzLmRhdGEuZnJhbWUoY292ZXJhZ2UpDQogIGNvbG5hbWVzKGNvdmVyYWdlKSA8LSAiY292ZXJhZ2UiDQogIA0KICAjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMNCiAgDQogICMjIyBub3ZlbHR5IGZvciBhIGdpdmVuIHVzZXI6IHJhdGlvIG9mIHVua25vd24gaXRlbXMgaW4gdGhlIHRvcC1uIGxpc3QgDQogIG5vdmVsdHlfdGFibGUgPC0gZGF0YS5mcmFtZSgpICMgYW4gZW1wdHkgZGF0YWZyYW1lLCB3aWxsIGJlIGZpbGxlZCB3aXRoIG5vdmVsdHkgdmFsdWVzDQogIGRmIDwtIGFzLmRhdGEuZnJhbWUobXgpDQogIHByZWRfSUJDRl9hbGxfdXNlciA8LSBwcmVkaWN0KG9iamVjdCA9IG1vZGVsX0lCQ0YsIG5ld2RhdGEgPSBycm0sIG4gPSBOLHR5cGU9InRvcE5MaXN0IikgIyBwcmVkaWN0IGZvciBhbGwgdXNlcnMNCiAgVE9QX05fbGlzdF9hbGxfdXNlciA8LSBzYXBwbHkocHJlZF9JQkNGX2FsbF91c2VyQGl0ZW1zLCBmdW5jdGlvbih4KSB7Y29sbmFtZXMobXgpW3hdfSkgIyB0b3AtbiBsaXN0IGZvciBhbGwgdXNlcnMNCiAgIyBkZl8xOiByZXBsYWNlIHRoZSBub3QgTkEgdmFsdWVzIHRvIHRoZSBjb3JyZXNwb25kaW5nIGNvbHVtbiBuYW1lIA0KICBmb3IoaSBpbiAxOmRpbShteClbMV0pew0KICAgIGRmX2kgPC0gYXMuZGF0YS5mcmFtZSh0KG14KSkjICANCiAgICBkZl9pJEZpbG0gPC0gY29sbmFtZXMobXgpDQogICAgZGZfaSA8LSBkZl9pWyxjKGksKGRpbShteClbMV0rMSkpXSAlPiUgZmlsdGVyKGNvbXBsZXRlLmNhc2VzKC4pKSAjIGxpc3Qgb2YgdXNlci1pIHJhdGVkIGZpbG1zDQogICAgZGZfaSRGaWxtIDwtIHJvd25hbWVzKGRmX2kpICMgYWRkIGEgbmV3IGNvbHVtbiB3aXRoIHRoZSBzYW1lIGNvbnRlbnQgb2Ygcm93bmFtZXMNCiAgICANCiAgICBkZl90b3BfbiA8LSBhcy5kYXRhLmZyYW1lKFRPUF9OX2xpc3RfYWxsX3VzZXJbLGldKSAgICMgdG9wLW4gbGlzdCBvZiB1c2VyLWkNCiAgICBjb2xuYW1lcyhkZl90b3BfbikgPC0gIkZpbG0iDQogICAgDQogICAgZGZfY3Jvc3MgPC0gaW5uZXJfam9pbihkZl9pLCBkZl90b3BfbiwgYnk9IkZpbG0iKSAgIyBpbm5lciBqb2luIHRoZSB0d28gZGF0YXNldCwgd2UgZ2V0IHRoZSByYXRlZCBpdGVtcyBpbiB0aGUgdG9wLW4gbGlzdA0KICAgIA0KICAgIG5vdmVsdHkgPC0gMSAtIGRpbShkZl9jcm9zcylbMV0vTiAgIyBub3ZlbHR5IHZhbHVlIG9mIHVzZXItaQ0KICAgIG5vdmVsdHlfdGFibGUgPC0gcmJpbmQobm92ZWx0eV90YWJsZSwgbm92ZWx0eSkNCiAgfQ0KICANCiAgbm92ZWx0eV90YWJsZSRVc2VySUQgPC0gcm93bmFtZXMobXgpDQogIGNvbG5hbWVzKG5vdmVsdHlfdGFibGUpIDwtIGMoIm5vdmVsdHkiLCJVc2VySUQiKQ0KICBub3ZlbHR5X3RhYmxlIDwtIG5vdmVsdHlfdGFibGUgJT4lIHNlbGVjdChVc2VySUQsbm92ZWx0eSkgIyBub3ZlbHR5IHRhYmxlDQogIA0KICAjIyMgcmVzdWx0IG9mIGFjY3VyYWN5LCBjb3ZlcmFnZSwgYW5kIG5vdmVsdHkNCiAgbXlfbGlzdCA8LSBsaXN0KCJhY2N1cmFjeSIgPSBhY2NfSUJDRiwiY292ZXJhZ2UiID0gY292ZXJhZ2UsICJub3ZlbHR5IiA9IG5vdmVsdHlfdGFibGUpDQogIHJldHVybihteV9saXN0KSANCn0NCg0KDQp0ZXN0IDwtIGNhbGNfdG9wbl9tZXRyaWNzKG14X3JlZHVjZWQsMC44LDIwKQ0KDQp0ZXN0JGFjY3VyYWN5O3Rlc3QkY292ZXJhZ2U7IHRlc3Qkbm92ZWx0eQ0KDQpgYGANCjExIEltcGxlbWVudGllcnVuZyBUb3AtTiBNb25pdG9yIEF1ZmdhYmUgRElZOiBVbnRlcnN1Y2hlIGRpZSByZWxhdGl2ZSDDnGJlcmVpbnN0aW1tdW5nIHp3aXNjaGVuIFRvcC1OIEVtcGZlaGx1bmdlbiB1bmQgcHLDpGZlcmllcnRlbiBGaWxtZW4gZsO8ciA0IHVudGVyc2NoaWVkbGljaGUgTW9kZWxsZSAoei5CLiBJQkNGIHVuZCBVQkNGIG1pdCB1bnRlcnNjaGllZGxpY2hlbiDDhGhubGljaGtlaXRzLW1ldHJpa2VuIC8gTmFjaGJhcnNjaGFmdGVuIHNvd2llIFNWRCBtaXQgdW50ZXJzY2hpZWRsaWNoZXIgRGltZW5zaW9uYWxpdMOkdHNyZWR1a3Rpb24pLg0KDQoxMS4xIEZpeGllcmUgMjAgenVmw6RsbGlnIGdld8OkaGx0ZSBUZXN0a3VuZGVuIGbDvHIgYWxsZSBNb2RlbGx2ZXJnbGVpY2hlLA0KYGBge3J9DQpzZXQuc2VlZCg1NzgpDQp0cmFpbl90ZXN0XzExIDwtIGV2YWx1YXRpb25TY2hlbWUocnJtX3JlZHVjZWQsIG1ldGhvZD0ic3BsaXQiLCB0cmFpbj0wLjk1LCBrPTEsIGdpdmVuPTIwLGdvb2RSYXRpbmc9NCkgDQoNCiMgdHJhaW5pbmcgZGF0YXNldCBoYXMgMzgwIHVzZXJzLHRlc3QgZGF0YXNldCBoYXMgMjAgdXNlcnMgDQojIGdpdmVuPTIwOiBGb3IgZWFjaCB0ZXN0IHVzZXIsIDIwIGZpbG1zIHBlciB1c2VyIHdpbGwgYmUgdXNlZCBmb3IgcHJlZGljdGlvbiwgdGhlIHJlc3QgZm9yIGV2YWx1YXRpb24pDQpycm1fcmVkdWNlZF90cmFpbl8xMSA8LSBnZXREYXRhKHRyYWluX3Rlc3RfMTEsInRyYWluIikNCnJybV9yZWR1Y2VkX2tub3duXzExIDwtIGdldERhdGEodHJhaW5fdGVzdF8xMSwia25vd24iKSANCnJybV9yZWR1Y2VkX3Vua25vd25fMTEgPC0gZ2V0RGF0YSh0cmFpbl90ZXN0XzExLCJ1bmtub3duIikNCg0KIyBJQ0JGIG1vZGVscw0KbW9kZWxfSUJDRl9jb3NfMTAgPC1SZWNvbW1lbmRlcihkYXRhID0gcnJtX3JlZHVjZWRfdHJhaW5fMTEsbWV0aG9kPSJJQkNGIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsbWV0aG9kPSJDb3NpbmUiLGs9MTApKQ0KbW9kZWxfSUJDRl9jb3NfNTAgPC1SZWNvbW1lbmRlcihkYXRhID0gcnJtX3JlZHVjZWRfdHJhaW5fMTEsbWV0aG9kPSJJQkNGIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsbWV0aG9kPSJDb3NpbmUiLGs9NTApKQ0KDQptb2RlbF9JQkNGX3BzXzEwIDwtUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluXzExLG1ldGhvZD0iSUJDRiIscGFyYW1ldGVyPWxpc3Qobm9ybWFsaXplID0gIlotc2NvcmUiLG1ldGhvZD0iUGVhcnNvbiIsaz0xMCkpDQptb2RlbF9JQkNGX3BzXzUwIDwtUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluXzExLG1ldGhvZD0iSUJDRiIscGFyYW1ldGVyPWxpc3Qobm9ybWFsaXplID0gIlotc2NvcmUiLG1ldGhvZD0iUGVhcnNvbiIsaz01MCkpDQoNCiMgVUJDRiBtb2RlbHMNCm1vZGVsX1VCQ0ZfY29zXzEwIDwtUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluXzExLG1ldGhvZD0iVUJDRiIscGFyYW1ldGVyPWxpc3Qobm9ybWFsaXplID0gIlotc2NvcmUiLG1ldGhvZD0iQ29zaW5lIixubj0xMCkpDQptb2RlbF9VQkNGX2Nvc181MCA8LVJlY29tbWVuZGVyKGRhdGEgPSBycm1fcmVkdWNlZF90cmFpbl8xMSxtZXRob2Q9IlVCQ0YiLHBhcmFtZXRlcj1saXN0KG5vcm1hbGl6ZSA9ICJaLXNjb3JlIixtZXRob2Q9IkNvc2luZSIsbm49NTApKQ0KDQptb2RlbF9VQkNGX3BzXzEwIDwtUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluXzExLG1ldGhvZD0iVUJDRiIscGFyYW1ldGVyPWxpc3Qobm9ybWFsaXplID0gIlotc2NvcmUiLG1ldGhvZD0iUGVhcnNvbiIsbm49MTApKQ0KbW9kZWxfVUJDRl9wc181MCA8LVJlY29tbWVuZGVyKGRhdGEgPSBycm1fcmVkdWNlZF90cmFpbl8xMSxtZXRob2Q9IlVCQ0YiLHBhcmFtZXRlcj1saXN0KG5vcm1hbGl6ZSA9ICJaLXNjb3JlIixtZXRob2Q9IlBlYXJzb24iLG5uPTUwKSkNCg0KIyBTVkQgbW9kZWxzDQptb2RlbF9TVkRfMTAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluXzExLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz0xMCkpDQptb2RlbF9TVkRfNTAgPC0gUmVjb21tZW5kZXIoZGF0YSA9IHJybV9yZWR1Y2VkX3RyYWluXzExLG1ldGhvZD0iU1ZEIixwYXJhbWV0ZXI9bGlzdChub3JtYWxpemUgPSAiWi1zY29yZSIsaz01MCkpDQoNCiMgZXZhbHVhdGlvbiBvZiB0aGUgcHJlZGljdGlvbnMNCmFjY19JQkNGX2Nvc18xMCA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfSUJDRl9jb3NfMTAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93bl8xMSwgbiA9IDE1LHR5cGU9InRvcE5MaXN0IikscnJtX3JlZHVjZWRfdW5rbm93bl8xMSxnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCmFjY19JQkNGX2Nvc181MCA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfSUJDRl9jb3NfNTAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93bl8xMSwgbiA9IDE1LHR5cGU9InRvcE5MaXN0IikscnJtX3JlZHVjZWRfdW5rbm93bl8xMSxnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCmFjY19JQkNGX3BzXzEwIDwtIGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocHJlZGljdChvYmplY3QgPSBtb2RlbF9JQkNGX3BzXzEwLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd25fMTEsIG4gPSAxNSx0eXBlPSJ0b3BOTGlzdCIpLHJybV9yZWR1Y2VkX3Vua25vd25fMTEsZ2l2ZW49MjAsZ29vZFJhdGluZyA9IDQpDQphY2NfSUJDRl9wc181MCA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfSUJDRl9wc181MCwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duXzExLCBuID0gMTUsdHlwZT0idG9wTkxpc3QiKSxycm1fcmVkdWNlZF91bmtub3duXzExLGdpdmVuPTIwLGdvb2RSYXRpbmcgPSA0KQ0KDQphY2NfVUJDRl9jb3NfMTAgPC0gY2FsY1ByZWRpY3Rpb25BY2N1cmFjeShwcmVkaWN0KG9iamVjdCA9IG1vZGVsX1VCQ0ZfY29zXzEwLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd25fMTEsIG4gPSAxNSx0eXBlPSJ0b3BOTGlzdCIpLHJybV9yZWR1Y2VkX3Vua25vd25fMTEsZ2l2ZW49MjAsZ29vZFJhdGluZyA9IDQpDQphY2NfVUJDRl9jb3NfNTAgPC0gY2FsY1ByZWRpY3Rpb25BY2N1cmFjeShwcmVkaWN0KG9iamVjdCA9IG1vZGVsX1VCQ0ZfY29zXzUwLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd25fMTEsIG4gPSAxNSx0eXBlPSJ0b3BOTGlzdCIpLHJybV9yZWR1Y2VkX3Vua25vd25fMTEsZ2l2ZW49MjAsZ29vZFJhdGluZyA9IDQpDQphY2NfVUJDRl9wc18xMCA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfVUJDRl9wc18xMCwgbmV3ZGF0YSA9IHJybV9yZWR1Y2VkX2tub3duXzExLCBuID0gMTUsdHlwZT0idG9wTkxpc3QiKSxycm1fcmVkdWNlZF91bmtub3duXzExLGdpdmVuPTIwLGdvb2RSYXRpbmcgPSA0KQ0KYWNjX1VCQ0ZfcHNfNTAgPC0gY2FsY1ByZWRpY3Rpb25BY2N1cmFjeShwcmVkaWN0KG9iamVjdCA9IG1vZGVsX1VCQ0ZfcHNfNTAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93bl8xMSwgbiA9IDE1LHR5cGU9InRvcE5MaXN0IikscnJtX3JlZHVjZWRfdW5rbm93bl8xMSxnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCg0KYWNjX1NWRF8xMCA8LSBjYWxjUHJlZGljdGlvbkFjY3VyYWN5KHByZWRpY3Qob2JqZWN0ID0gbW9kZWxfU1ZEXzEwLCBuZXdkYXRhID0gcnJtX3JlZHVjZWRfa25vd25fMTEsIG4gPSAxNSx0eXBlPSJ0b3BOTGlzdCIpLHJybV9yZWR1Y2VkX3Vua25vd25fMTEsZ2l2ZW49MjAsZ29vZFJhdGluZyA9IDQpDQphY2NfU1ZEXzUwIDwtIGNhbGNQcmVkaWN0aW9uQWNjdXJhY3kocHJlZGljdChvYmplY3QgPSBtb2RlbF9TVkRfNTAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93bl8xMSwgbiA9IDE1LHR5cGU9InRvcE5MaXN0IikscnJtX3JlZHVjZWRfdW5rbm93bl8xMSxnaXZlbj0yMCxnb29kUmF0aW5nID0gNCkNCg0KYWNjX3RhYmxlIDwtIHJiaW5kKGFjY19JQkNGX2Nvc18xMCxhY2NfSUJDRl9jb3NfNTAsYWNjX0lCQ0ZfcHNfMTAsYWNjX0lCQ0ZfcHNfNTAsYWNjX1VCQ0ZfY29zXzEwLGFjY19VQkNGX2Nvc181MCxhY2NfVUJDRl9wc18xMCxhY2NfVUJDRl9wc181MCxhY2NfU1ZEXzEwLGFjY19TVkRfNTApDQoNCmFjY190YWJsZQ0KYGBgDQojIyMgSW4gdGhlIElCQ0YgbW9kZWwsIGJvdGggcHJlY2lzaW9uIGFuZCByZWNhbGwgYXJlIGJldHRlciB3aXRoIGNvc2luZSBtZXRob2QgYW5kIDUwIG5laWdoYm9ycy4NCiMjIyBJbiB0aGUgVUJDRiBtb2RlbCwgY29zaW5lIG1ldGhvZCBhbmQgMTAgbmVpZ2hib3JzIGlzIGEgYmV0dGVyIGNvbWJpbmF0aW9uLg0KIyMjIEluIHRoZSBTVkQgbW9kZWwsIHByZWNpc2lvbiBhbmQgcmVjYWxsIGFyZSBiZXR0ZXIgd2l0aCBzaW5ndWxhciB2YWx1ZSBvZiAxMC4gDQojIyMgVGhyb3VnaCBhbGwgdGhlIG1vZGVscywgVGhlIFNWRCBtb2RlbCB3aXRoIHNpbmd1bGFyIHZhbHVlIG9mIDEwIGhhcyB0aGUgYmVzdCBwcmVjaXNpb24gKDAuNDYzKSBhbmQgcmVjYWxsICgwLjA3NzkpLg0KDQoNCg0KMTEuMiBCZXN0aW1tZSBkZW4gQW50ZWlsIGRlciBUb3AtTiBFbXBmZWhsdW5nIG5hY2ggR2VucmVzIHBybyBLdW5kZSwNCg0KYGBge3J9DQpUb3Bfbl9nZW5yZSA8LSBmdW5jdGlvbihUb3Bfbl9saXN0LG4peyAgICMgbXggaXMgdXNlci1pdGVtIG1hdHJpeDsgVG9wX25fbGlzdDogdG9wLW4gbWF0cml4OyBuOiB0aGUgIm4iIGluIHRvcC1uIA0KICANCiAgdGFibGUgPSBkYXRhLmZyYW1lKCkNCiAgZm9yKGkgaW4gMTpkaW0oVG9wX25fbGlzdClbMl0pew0KICAgIGRmX3RvcCA8LSBhcy5kYXRhLmZyYW1lKFRvcF9uX2xpc3RbLGldKQ0KICAgIGNvbG5hbWVzKGRmX3RvcCkgPC0gIkZpbG0iDQogICAgDQogICAgZGZfZmlsbV9nZW5yZV8xIDwtIGFzLmRhdGEuZnJhbWUobXhfZmlsbV9nZW5yZSkNCiAgICBkZl9maWxtX2dlbnJlXzEkRmlsbSA8LSByb3duYW1lcyhkZl9maWxtX2dlbnJlXzEpDQogICAgDQogICAgZGZfdG9wIDwtIGxlZnRfam9pbihkZl90b3AsZGZfZmlsbV9nZW5yZV8xLGJ5PSgiRmlsbSIpKSAlPiUgc2VsZWN0KC1GaWxtKQ0KICAgIGRmX3RvcCA8LSBkZl90b3BbLTEsXSANCiAgICB0b3RhbCA8LSBzdW0oZGZfdG9wKQ0KICAgIGRmX3RvcFsicmF0aW8iLF0gPC0gY29sU3VtcyhkZl90b3ApL3RvdGFsDQogICAgZGZfdG9wIDwtIGRmX3RvcFsicmF0aW8iLF0NCg0KICAgIHRhYmxlIDwtIHJiaW5kKHRhYmxlLGRmX3RvcCkNCiAgfQ0KICByb3duYW1lcyh0YWJsZSkgPC0gY29sbmFtZXMoVG9wX25fbGlzdCkNCiAgcmV0dXJuKHRhYmxlKQ0KfQ0KDQoNCiMgVG9wLTE1IHJlY29tbWVuZGF0aW9uIGxpc3Qgb2YgU1ZEIHdpdGggayA9IDEwDQpQcmVkX1NWRF9rMTAgPC0gcHJlZGljdChvYmplY3QgPSBtb2RlbF9TVkRfMTAsIG5ld2RhdGEgPSBycm1fcmVkdWNlZF9rbm93bl8xMSwgbiA9IDE1LHR5cGU9YygidG9wTkxpc3QiKSkNClRvcDE1X1NWRCA8LSBzYXBwbHkoUHJlZF9TVkRfazEwQGl0ZW1zLCBmdW5jdGlvbih4KSB7Y29sbmFtZXMoZGZfcmVkdWNlZClbeF19KQ0KDQpUb3BfMTVfcmVjb21tZW5kYXRpb25zIDwtIFRvcF9uX2dlbnJlKFRvcDE1X1NWRCwxNSkgIyB0aGUgcGVyY2VudGFnZSBvZiB0b3AtMTUgcmVjb21tZW5kYXRpb25zIGJ5IGdlbnJlIHBlciB0ZXN0IHVzZXINCg0KVG9wXzE1X3JlY29tbWVuZGF0aW9ucztzdW1tYXJ5KHJvd1N1bXMoVG9wXzE1X3JlY29tbWVuZGF0aW9ucykpWy00XSAjIGNoZWNrIGlmIHRoZSB0b3RhbCBnZW5yZSByYXRpbyBmb3IgZWFjaCB1c2VyID0gMQ0KDQpgYGANCiMjIyBUaGUgdGFibGUgc2hvd3MgdGhlIHBlcmNlbnRhZ2Ugb2YgZ2VucmVzIGluIHRoZSB0b3AtMTUgcmVjb21tZW5kYXRpb24gbGlzdCBwZXIgdXNlci4NCiMjIyBUaGUgc3VtIG9mIGVhY2ggcm93IGFyZSBhbGwgMSwgdGhpcyBpbmRpY2F0ZXMgdGhlIHRvdGFsIHJhdGlvIG9mIGVhY2ggdXNlciBhcmUgYWxsIGNvcnJlY3QuIA0KDQoNCg0KMTEuMyBCZXN0aW1tZSBwcm8gS3VuZGUgZGVuIEFudGVpbCBuYWNoIEdlbnJlcyBzZWluZXIgVG9wLUZpbG1lICg9RmlsbWUsIHdlbGNoZSB2b20gS3VuZGVuIGRpZSBiZXN0ZW4gQmV3ZXJ0dW5nZW4gZXJoYWx0ZW4gaGFiZW4pDQoNCmBgYHtyfQ0KVG9wX2ZpbG1fZ2VucmUgPC0gZnVuY3Rpb24obXgsbil7ICAgIyBteCBpcyB1c2VyLWl0ZW0gbWF0cml4LCBuOiB0b3AtbiByYXRlZCBmaWxtcw0KICANCiAgdGFibGUgPSBkYXRhLmZyYW1lKCkNCiAgZm9yKGkgaW4gMTpkaW0obXgpWzFdKXsNCiAgICBkZl90b3AgPC0gYXMuZGF0YS5mcmFtZSh0KG14KSkNCiAgICBkZl90b3AkRmlsbSA8LSByb3duYW1lcyhkZl90b3ApDQogICAgZGZfdG9wIDwtIGRmX3RvcFssYyhpLChkaW0obXgpWzFdKzEpKV0NCiAgICBjb2xuYW1lcyhkZl90b3ApIDwtIGMoIlJhdGluZ3MiLCJGaWxtIikNCiAgICBkZl90b3AgPC0gZGZfdG9wICU+JSBmaWx0ZXIoY29tcGxldGUuY2FzZXMoLikpICU+JSBhcnJhbmdlKGRlc2MoUmF0aW5ncykpICU+JSBzbGljZSgxOm4pDQogICAgDQogICAgZGZfZmlsbV9nZW5yZV8xIDwtIGFzLmRhdGEuZnJhbWUobXhfZmlsbV9nZW5yZSkNCiAgICBkZl9maWxtX2dlbnJlXzEkRmlsbSA8LSByb3duYW1lcyhkZl9maWxtX2dlbnJlXzEpDQogICAgDQogICAgZGZfbGVmdF9qb2luIDwtIGxlZnRfam9pbihkZl90b3AsZGZfZmlsbV9nZW5yZV8xLGJ5PSgiRmlsbSIpKQ0KICAgIA0KICAgIGRmX3RvcCA8LSBkZl9sZWZ0X2pvaW5bLC0oMToyKV0gDQogICAgdG90YWwgPC0gc3VtKGRmX3RvcCkNCiAgICBkZl90b3BbInJhdGlvIixdIDwtIGNvbFN1bXMoZGZfdG9wKS90b3RhbA0KICAgIGRmX3RvcCA8LSBkZl90b3BbInJhdGlvIixdDQogICAgdGFibGUgPC0gcmJpbmQodGFibGUsZGZfdG9wKQ0KICB9DQogIHJvd25hbWVzKHRhYmxlKSA8LSByb3duYW1lcyhteCkNCiAgcmV0dXJuKHRhYmxlKQ0KfQ0KDQpUb3BfMTVfZmlsbXMgPC0gVG9wX2ZpbG1fZ2VucmUobXhfcmVkdWNlZCwxNSkgIyBnZW5yZXMgcHJvcG9ydGlvbiBvZiB0aGUgdG9wIDE1IGZpbG1zIGZvciBldmVyeSB1c2VyDQpUb3BfMTVfZmlsbXMNCmBgYA0KYGBge3J9DQpzdW1tYXJ5KHJvd1N1bXMoVG9wXzE1X2ZpbG1zKSlbLTRdDQpgYGANCiMjIyBUaGUgZmlyc3QgdGFibGUgc2hvd3MgdGhlIHBlcmNlbnRhZ2Ugb2YgZ2VucmVzIGluIHRoZSB0b3AtMTUgcmF0ZWQgbGlzdCBwZXIgdXNlci4NCiMjIyBUaGUgc3VtIG9mIGVhY2ggcm93IGFyZSBhbGwgMSwgdGhpcyBpbmRpY2F0ZXMgdGhlIHRvdGFsIHJhdGlvIG9mIGVhY2ggdXNlciBhcmUgYWxsIGNvcnJlY3QuIA0KDQoNCg0KMTEuNCBWZXJnbGVpY2hlIHBybyBLdW5kZSBUb3AtRW1wZmVobHVuZ2VuIHVuZCBUb3AtRmlsbWVuIG5hY2ggR2VucmVzLCANCg0KYGBge3J9DQojIGZpbHRlciB0aGUgVG9wLUZpbG1lbiB3aXRoIHRoZSB1c2VycyBvbmx5IGFwcGVhciBpbiB0aGUgVG9wLXJlY29tbWVuZGF0aW9uDQpUb3BfMTVfZmlsbXNfcmVkdWNlZCA8LSBUb3BfMTVfZmlsbXMNClRvcF8xNV9maWxtc19yZWR1Y2VkJFVzZXJJRCA8LSByb3duYW1lcyhUb3BfMTVfZmlsbXNfcmVkdWNlZCkNClRvcF8xNV9maWxtc19yZWR1Y2VkIDwtIFRvcF8xNV9maWxtc19yZWR1Y2VkICU+JSBmaWx0ZXIoVXNlcklEICVpbiUgcm93bmFtZXMoVG9wXzE1X3JlY29tbWVuZGF0aW9ucykpICU+JSBzZWxlY3QoLVVzZXJJRCkgIyB3aXRoIDIwIHVzZXJzDQoNCiMgY2FsY3VsYXRlIHRoZSBtZWFuIGFic29sdXRlIGVycm9yDQpNQUVfdG9wX2dlbnJlIDwtIHJvd1N1bXMoYWJzKFRvcF8xNV9maWxtc19yZWR1Y2VkIC0gVG9wXzE1X3JlY29tbWVuZGF0aW9ucykpLzIwDQoiTUFFIGJldHdlZW4gVG9wLXJlY29tbWVuZGF0aW9ucyBhbmQgVG9wLWZpbG1zIGJ5IGdlbnJlcyBwZXIgdXNlcjoiOyBNQUVfdG9wX2dlbnJlOyJ0aGUgZml2ZSBudW1iZXIgc3RhdGlzdGljcyBvZiB0aGUgTUFFOiI7c3VtbWFyeShNQUVfdG9wX2dlbnJlKVstNF0NCmBgYA0KDQoNCmBgYHtyfQ0KIk1TRSBiZXR3ZWVuIFRvcC1yZWNvbW1lbmRhdGlvbnMgYW5kIFRvcC1maWxtcyBieSBnZW5yZXMgcGVyIHVzZXI6Ig0KTVNFX3RvcF9nZW5yZSA8LSByb3dTdW1zKChUb3BfMTVfZmlsbXNfcmVkdWNlZCAtIFRvcF8xNV9yZWNvbW1lbmRhdGlvbnMpXjIpLzIwDQpNU0VfdG9wX2dlbnJlOyJ0aGUgZml2ZSBudW1iZXIgc3RhdGlzdGljcyBvZiB0aGUgTVNFOiI7c3VtbWFyeShNU0VfdG9wX2dlbnJlKVstNF0NCmBgYA0KDQoNCmBgYHtyfQ0KIlJNU0UgYmV0d2VlbiBUb3AtcmVjb21tZW5kYXRpb25zIGFuZCBUb3AtZmlsbXMgYnkgZ2VucmVzIHBlciB1c2VyOiINClJNU0VfdG9wX2dlbnJlIDwtIHNxcnQocm93U3VtcygoVG9wXzE1X2ZpbG1zX3JlZHVjZWQgLSBUb3BfMTVfcmVjb21tZW5kYXRpb25zKV4yKS8yMCkNClJNU0VfdG9wX2dlbnJlOyJ0aGUgZml2ZSBudW1iZXIgc3RhdGlzdGljcyBvZiB0aGUgUk1TRToiO3N1bW1hcnkoUk1TRV90b3BfZ2VucmUpWy00XQ0KDQpgYGANCiMjIyBUaHJlZSBxdWFudGl0YXRpdiBtZXRyaWNzIE1BRShtZWFuIGF2ZXJhZ2UgZXJyb3IpLCBNU0UobWVhbiBzcXVhcmVkIGVycm9yKSwgUk1TRSh0aGUgcm9vdCBtZWFuIHNxdWFyZWQgZXJyb3IpIHdlcmUgdXNlZCB0byBjb21wYXJlIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIHRvcC1yZWNvbW1lbmRhdGlvbnMgYW5kIHRvcC1yYXRlZC1maWxtcyBieSBnZW5yZXMuDQoNCg0KDQoxMS41IERlZmluaWVyZSBlaW5lIFF1YWxpdMOkdHNtZXRyaWsgZsO8ciBUb3AtTiBMaXN0ZW4gdW5kIHRlc3RlIHNpZS4gDQoNCmBgYHtyfQ0KIyBNQVA6IEF2ZXJhZ2UgUHJlY2lzaW9uIGFuZCBNZWFuIEF2ZXJhZ2UgUHJlY2lzaW9uDQoNCk1BUCA8LSBmdW5jdGlvbihteCxUb3Bfbl9saXN0LG4pew0KICAjIGV4dHJhY3QgdGhlIHVzZXJzIGluIHRoZSBUb3AtbiBsaXN0cywgb3IgdXNlIGRpcmVjdCB0aGUgdGVzdCBkYXRhc2V0Lg0KICBteF9wYXJ0IDwtIGFzLmRhdGEuZnJhbWUobXgpICU+JSBmaWx0ZXIocm93bmFtZXMoYXMuZGF0YS5mcmFtZShteCkpICVpbiUgY29sbmFtZXMoYXMuZGF0YS5mcmFtZShUb3Bfbl9saXN0KSkpIyB1c2VyX2ZpbG0NCiAgbXhfcGFydCA8LSBhcy5kYXRhLmZyYW1lKHQobXhfcGFydCkpICMgdHJhbnNwb3NlIG14X3BhcnRfdXNlcnMgdG8gZmlsbV91c2VyDQogIG14X3BhcnQkRmlsbSA8LSByb3duYW1lcyhteF9wYXJ0KSAjIGdlbmVyYXRlIG5ldyBjb2x1bW4gIkZpbG0iIHNhbWUgYXMgdGhlIHJvd25hbWVzDQogIFRvcF9uX2xpc3QgPC0gYXMuZGF0YS5mcmFtZShUb3Bfbl9saXN0KQ0KICBUb3Bfbl9saXN0JFJhbmsgPC0gMTpuICMgZ2VuZXJhdGUgbmV3IGNvbHVtbiAiUmFuayIgdG8gcmVwcmVzZW50IHRoZSByYW5rcyBvZiB0aGUgcmVjb21tZW5kZWQgZmlsbXMNCiAgDQogIHN1bW1lX3ByZWNpc2lvbiA8LSAwDQogIGZvcihpIGluIChkaW0obXhfcGFydClbMl0tMSkpew0KICAgIFRvcF9pIDwtIFRvcF9uX2xpc3RbLGMoYWxsX29mKGkpLGRpbShUb3Bfbl9saXN0KVsyXSldICMgZXh0cmFjdCB0aGUgdG9wX25fbGlzdCBhbmQgcmFuayBvZiB0aGUgaS10aCB1c2VyDQogICAgY29sbmFtZXMoVG9wX2kpIDwtIGMoIkZpbG0iLCJSYW5rIikgIyByZW5hbWUgdGhlIGNvbHVtbnMgYXMgIkZpbG0iIGFuZCAiUmFuayINCiAgICBteF9pIDwtIG14X3BhcnQgJT4lIHNlbGVjdChjKGFsbF9vZihpKSxkaW0obXhfcGFydClbMl0pKSAgICAgICAjIG14X2k6IGV4dHJhY3QgdGhlIHJhdGluZ3MgYW5kIEZpbG0gbmFtZXMgb2YgaS10aCB1c2VyIGZyb20gcmF0aW5nIG1hdHJpeA0KICAgIGNvbG5hbWVzKG14X2kpIDwtIGMoIlJhdGluZyIsIkZpbG0iKQ0KICAgIG14X2pvaW4gPC0gbGVmdF9qb2luKFRvcF9pLG14X2ksYnk9IkZpbG0iKSAlPiUgZmlsdGVyKFJhdGluZz4zKSAjIGxlZnRfam9pbiB0aGUgcmF0aW5ncyB0byB0aGUgVG9wLW4gbGlzdCBieSAiRmlsbSIuIG14XzEgaGFzIHRoZSBjb2x1bW5zIG9mICJGaWxtIiwgIlJhbmsiLCBhbmQgcmF0aW5nczsgZmlsdGVyIHRoZSByZWxldmFudCBpdGVtcyAocmF0aW5ncyBncmVhdGVyIHRoYW4gMyk7IA0KICAgIG14X2pvaW4gPC0gbXhfam9pbiAlPiUgbXV0YXRlKE51bWVyYXRvciA9IDE6ZGltKG14X2pvaW4pWzFdLFByZWNpc2lvbiA9IE51bWVyYXRvci9SYW5rKSAjIGdlbmVyYXRlIG5ldyBjb2x1bW4gIk51bWVyYXRvciIgd2hpY2ggaXMgYSBuZXcgcmFuayBvbmx5IGZvciB0aGUgcmVsZXZhbnQgaXRlbXMsIGFuZCBuZXcgY29sdW1uICJQcmVjaXNpb24iIHdoaWNoIGlzIHRoZSBQcmVjaXNpb24gb2YgZXZlcnkgcmVsZXZhbnQgaXRlbXMuDQoNCiAgICBhdmdfdXNlcl9pX3ByZWNpc2lvbiA8LSBtZWFuKG14X2pvaW4kUHJlY2lzaW9uKSAgIyBhdmVyYWdlIHByZWNpc2lvbiBvZiB1c2VyLWkNCiAgICBzdW1tZV9wcmVjaXNpb24gPC0gc3VtbWVfcHJlY2lzaW9uICsgYXZnX3VzZXJfaV9wcmVjaXNpb24NCiAgfQ0KICBtYXAgPC0gc3VtbWVfcHJlY2lzaW9uLyhkaW0oVG9wX25fbGlzdClbMl0tMSkgIyBtZWFuIGF2ZXJhZ2UgcHJlY2lzaW9uDQogIHJldHVybihtYXApDQp9DQoNCk1BUChteF9yZWR1Y2VkLFRPUDE1X0lCQ0YsMTUpDQpgYGANCiMjIyBmaXJzdGx5LCBmb3Igb25lIHVzZXIsIGZpbmQgb3V0IHRoZSByYW5rIG9mIHRoZSBtLXRoIHJlbGV2YW50IGl0ZW0gKHJhdGluZyA+IDMpIGluIHRoZSB0b3Bfbl9saXN0LCB0aGVuIGNhbGN1bGF0ZSB0aGUgcHJlY2lzaW9uOiBtL24uDQojIyMgc2Vjb25kbHksIGNhbGN1bGF0ZSB0aGUgcHJlY2lzaW9ucyBvZiBhbGwgcmVsZXZhbnQgaXRlbXMuDQojIyMgdGhlIGF2ZXJhZ2UgcHJlY2lzaW9uIG9mIG9uZSB1c2VyOiBhdmVyYWdlIGFsbCB0aGUgcHJlY2lzaW9uIG9mIHJlbGV2YW50IGl0ZW1zLg0KIyMjIE1BUDogYXZlcmFnZSBwcmVjaXNpb24gb2YgYWxsIHVzZXJzLg==